Strona główna › Języki, automaty i obliczenia - zbiór zadań

Gramatyki bezkontekstowe

pon., 03/21/2011 - 14:36 — ciebie
  1. Podać gramatyki bezkontekstowe generujące następujące języki:
    1. zbiór słów nad alfabetem \(\{ a,b\}\), które zawierają tyle samo \(a\) co \(b\);

    2. zbiór słów nad alfabetem \(\{ a,b\}\), które zawierają dwa razy więcej \(a\) niż \(b\);

    3. zbiór słów nad alfabetem \(\{ a,b\}\) o długości parzystej, w których liczba wystąpień litery \(b\) na pozycjach parzystych jest równa liczbie wystąpień tej litery na pozycjach nieparzystych;

    4. zbiór wyrażeń arytmetycznych nad alfabetem \(\{ 0,1,(,),+,\cdot\}\), które, przy zwykłej interpretacji działań dla liczb naturalnych, mają wartość 3;
    5. zbiór wyrażeń arytmetycznych w notacji polskiej (nad alfabetem \(\{ 0,1,+,\cdot\}\)) o wartości 4;
    6. zbiór poprawnie zbudowanych formuł rachunku zdań ze zmienną zdaniową \(p\) i stałymi logicznymi true, false (alfabet: \(\{ p,\mbox{true},\mbox{false},\wedge,\vee,\neg,(,)\}\));
    7. zbiór tych formuł z poprzedniego punktu, które przy każdym wartościowaniu zmiennej \(p\) mają wartość logiczną prawda (tzn.  tautologii);
    8. \(\{ a^{i}b^{j}c^{k}\,:\, i\neq j\,\vee\, j\neq k\}\);
    9. \(\{ a^{i}b^{j}a^{k}\,:\, i+k=j\}\);
    10. \(\{ a^{i}b^{j}c^{p}d^{q}:\ i,j,p,q>0,\ i+j=p+q\ \}\).
  2. Dla danych gramatyk bezkontekstowych \(G,H\), skonstruować gramatyki generujące języki \(L(G)\cup L(H)\), \(L(G)L(H)\), \((L(G))^{*}\), \((L(G))^{R}\) (=lustrzane odbicie).
  3. Wykazać, że zbiór palindromów nad ustalonym alfabetem jak również jego dopełnienie są językami bezkontekstowymi.
  4. Napisać gramatykę bezkontekstową (jak najkrótszą) generującą język:
    \(L\ =\ \{\ a^{i}b^{j}\ :\ i,j\ge 1;\ i< 2j-1\ \}\)
  5. Skonstruować gramatykę bezkontekstową z jednym symbolem nieterminalnym generującą zbiór \(\{ x\in(a+b)^{*}\ :\ \# _{a}(x)=\# _{b}(x)\ \}\), gdzie \(\# _{s}(w)\) oznacza liczbę wystąpień symbolu \(s\) w słowie \(w\).

  6. Skonstruować gramatykę bezkontekstową jednoznaczną generującą język \(\mathbf{D_{1}}\) poprawnie uformowanych wyrażeń nawiasowych (por. Rozdział ??, Zadanie ?? ).

  7. Napisać gramatyki bezkontekstowe generujace zbiór tych słów z języka \(\mathbf{D_{1}}\), które

    1. zawierają parzystą liczbę (np. 0) nawiasów otwierających,

    2. nie zawierają podsłowa (()).

  8. Skonstruować gramatykę bezkontekstową jednoznaczną generującą język z Zadania ??.

    Wskazówka. Rozważyć gramatykę

    \(\displaystyle Z \rightarrow ZaZ^{+}b\,|\, ZbZ^{-}a\,|\,\varepsilon\)

    \(\displaystyle Z^{+} \rightarrow Z^{+}aZ^{+}b\,|\,\varepsilon\)

    \(\displaystyle Z^{-} \rightarrow Z^{-}bZ^{-}a\,|\,\varepsilon\)

    Zauważyć związek miedzy produkcjami dla \(Z^{+}\) a poprzednim zadaniem (podobnie dla \(Z^{-}\)).

  9. Dowieść, że następujące warunki są równoważne dla języka \(L\subseteq\Sigma^{*}\):

    1. \(L\) jest regularny,

    2. \(L\) jest generowany przez gramatykę bezkontekstową, w której każda reguła jest postaci \(X\rightarrow\epsilon\), \(X\rightarrow Y\), lub \(X\rightarrow\sigma Y\), \(\sigma\in\Sigma\),
    3. \(L\) jest generowany przez gramatykę bezkontekstową, w której każda reguła jest postaci \(X\rightarrow\epsilon\), \(X\rightarrow Y\), lub \(X\rightarrow Y\sigma\), \(\sigma\in\Sigma\),
    4. \(L\) jest generowany przez gramatykę bezkontekstową, w której każda reguła jest postaci \(X\rightarrow\alpha\) lub \(X\rightarrow\beta Y\), \(\alpha,\beta\in\Sigma^{*}\).
  10. Podać przykład gramatyki bezkontekstowej w której każda reguła jest postaci \(X\rightarrow\epsilon\), \(X\rightarrow Y\), \(X\rightarrow\sigma Y\) lub \(X\rightarrow Y\sigma\), \(\sigma\in\Sigma\), ale język generowany przez gramatykę nie jest regularny.
  11. Czy każdy język bezkontekstowy jest generowany przez gramatykę w postaci z poprzedniego zadania?
  12. Powiemy, że gramatyka \(G\) ma własność właściwego samozapętlenia, jeśli dla pewnej zmiennej \(X\) zachodzi \(X\stackrel{G}{\rightarrow}^{*}\alpha X\beta\), gdzie \(\alpha,\beta\neq\epsilon\). Udowodnij, że gramatyka bezkontekstowa nie mająca własności właściwego samozapętlenia generuje język regularny.
  13. Udowodnij, że każdy język bezkontekstowy nad jednoliterowym alfabetem jest regularny.
  14. Udowodnij, że jeśli \(L\) jest bezkontekstowy to język \(\{ a^{{|w|}}\ :\ w\in L\}\) jest regularny.
  15. Niech \(G\) będzie gramatyką bezkontekstową, z \(m\) zmiennymi i niech, dla każdej reguły \(Y\stackrel{G}{\rightarrow}w\), \(|w|\leq\ell\). Dowieść, że jeśli \(X^{I}\stackrel{G*}{\rightarrow}\epsilon\), to istnieje wyprowadzenie o długości \(1+\ell+\ell^{2}+\ldots+\ell^{{m-1}}\). Czy to oszacowanie jest optymalne?
  16. Dowieść, że dla każdej gramatyki \(G\) istnieje stała \(C\), taka, że dla dowolnego \(w\neq\epsilon\), jeśli \(X_{I}\stackrel{G*}{\rightarrow}w\), to istnieje wyprowadzenie o długości \(\leq C\cdot|w|\).
  17. Załóżmy, że mamy pewną skończoną liczbę reguł wymazujących postaci \(\alpha\rightarrow\epsilon\). Stosując takie reguły możemy w danym słowie zastępować słowo \(\alpha\) przez słowo puste. Niech \(L\) będzie zbiorem słów, które możemy przekształcić na słowo puste stosując reguły wymazywania.

    Czy zawsze istnieje gramatyka bezkontekstowa generująca \(L\) i mająca tylko jeden symbol nieterminalny ?

  18. Zaprojektować algorytm, który, dla danej gramatyki \(G\), odpowiada na pytanie, czy język \(L(G)\) jest nieskończony.
  19. Udowodnij, że każdy język bezkontekstowy może być generowany przez gramatykę w której każdy symbol nieterminalny (poza być może symbolem początkowym) generuje nieskończenie wiele słów terminalnych.