Помощ за задача

[bojestven]

Моля ви помогнете ми за тази задача, никак не ги разбирам а утре имам изпит

[Реклама]

[NoThanks]

Имаш граматика с начален нетерминал S и крайна азбука А. Имаш, че S дефинира по следните начини:
1) [tex]S \to \varepsilon[/tex] т.е S е празната дума
2) [tex]S \to A[/tex]
За А пък имаме
1) [tex]A \to babAa[/tex]
2) [tex]A \to cc[/tex]
Сега като прилагаме правило 2) за S получаваме думи от типа S = babAa , където и за А имаме правило. Ясно е, че можем да прилагаме правилата за А до безкрайност. При ново прилагане получаваме S = babbabAaa ; S = babbabbabAaaa и тн. като крайната цел е да получим дума, в която не фигурира А.(другият случай е когато S e празната дума). Тогава за езикът L имаме :[tex]L=\{ \;, cc, babcca, babbabccaa, babbabbabccaaa, ... \; \}[/tex]
Ще е доволно, ако някой покаже как стават б) и в), че аз не съм много навътре в нещата и засега успях само да докажа каква граматика НЕ е за б) , а за в) нямам идея

[masterfromkardjali]

Граматиката е контекстно-свободна, т.к. имаш продукция в която А седи по средата. Това значи от тип 2 на Чомски-йерархията. За автомат, не мога да ти помогна все още, т.к. за тип 2 не съм учил как се построява. Мога само да кажа, че не е FSM, a Stackmaschine. Другия семестър, ако няма отговор ще ти отговоря

[NoThanks]

То това достатъчно ли било Аз се опитвах да го докажа с pumping лемата, но нещо не ми излизаше Сега като се замисля, aко си положим [tex]bba = v \; ; a = y \; ; a=z \;ba = u \; ; bcc= x [/tex] имаме, че [tex]|vy| \ge 1 \; |vxy| \le p \le |S|[/tex] и [tex]uv^{i}xy^{i}z[/tex] е в L

[masterfromkardjali]