zbiór słów nad alfabetem \(\{ a,b\}\), które zawierają dwa razy więcej \(a\) niż \(b\);
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;
Skonstruować gramatykę bezkontekstową jednoznaczną generującą język \(\mathbf{D_{1}}\) poprawnie uformowanych wyrażeń nawiasowych (por. Rozdział ??, Zadanie ?? ).
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^{*}\):
\(L\) jest regularny,
Czy zawsze istnieje gramatyka bezkontekstowa generująca \(L\) i mająca tylko jeden symbol nieterminalny ?