1. Podaj gramatykę generującą język \(\displaystyle{ \left\{ a^kb^ma^n : \text{k,m,n są nieujemne i takie że } k+m\neq n\right\}}\). Uzasadnij poprawność podanej gramatyki..
2. Napisz gramatykę generującą wszystkie liczby naturalne w zapisie dwójkowym, które mają tę samą liczbę jedynek na parzystych i nieparzystych miejscach..
bardzo byłbym wdzięczny za naprowadzenie jak zrobić te zadanka.. ale też nie tak skrótowo myślowo, bo nie najlepiej mi wychodzą gramatyki.. jak do nich podchodzić chyba niestety nie ma algorytmu
-- 15 lis 2011, o 21:48 --
w 1. myślę że trzeba to podzielić jakoś tak:
\(\displaystyle{ S \rightarrow S_1 | S_2}\)
\(\displaystyle{ S}\) - symbol startowy
\(\displaystyle{ S_1}\)- sytuacja: \(\displaystyle{ k+m>n}\)
\(\displaystyle{ S_2}\)- sytuacja: \(\displaystyle{ k+m<n}\)
nie wiem czy tak ładnie jest czy nie, ale chyba trzeba to jakoś rozbić na przypadki.. inaczej sobie nie wyobrażam..