Gramatyki bezkontekstowe | Informatyka MIMUW

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\ \}$ .
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).
Wykazać, że zbiór palindromów nad ustalonym alfabetem jak również jego dopełnienie są językami bezkontekstowymi.
Napisać gramatykę bezkontekstową (jak najkrótszą) generującą język:
$L\ =\ \{\ a^{i}b^{j}\ :\ i,j\ge 1;\ i< 2j-1\ \}$
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$ .
Skonstruować gramatykę bezkontekstową jednoznaczną generującą język $\mathbf{D_{1}}$ poprawnie uformowanych wyrażeń nawiasowych (por. Rozdział ??, Zadanie ?? ).
Napisać gramatyki bezkontekstowe generujace zbiór tych słów z języka D1, które
1. zawierają parzystą liczbę (np. 0) nawiasów otwierających,
2. nie zawierają podsłowa (()).
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^{-}$ ).
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^{*}$ .
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.
Czy każdy język bezkontekstowy jest generowany przez gramatykę w postaci z poprzedniego zadania?
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.
Udowodnij, że każdy język bezkontekstowy nad jednoliterowym alfabetem jest regularny.
Udowodnij, że jeśli $L$ jest bezkontekstowy to język $\{ a^{{|w|}}\ :\ w\in L\}$ jest regularny.
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?
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|$ .
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 ?
Zaprojektować algorytm, który, dla danej gramatyki $G$ , odpowiada na pytanie, czy język $L(G)$ jest nieskończony.
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.