найти, является ли строка с четным числом нулей а) контекстно-свободной б) регулярной
а) используя лемму о накачке для CFL.... это можно представить как e(0n)e(0n)e. Итак, это КЛЛ.
б) это может быть представлено как (00)* в регулярном выражении. Итак, я думаю, что это обычный язык. Но я не могу доказать то же самое, используя лемму о накачке для обычных языков.
Любая помощь приветствуется. Спасибо!!
0^n0^nдля n ›= 0 является регулярным языком, который может быть представлен RE(00)*, это0^n1^nне является регулярным (а CFL). - person Grijesh Chauhan schedule 07.04.2014"But, I am not able to prove the same using pumping lemma for regular languages."Вы не можете использовать лемму о накачке, чтобы доказать, что язык является обычным языком. -- Мы используем лемму прокачки, чтобы доказать, что язык не является обычным языком. Это необходимое, но достаточное свойство регулярного языка. Вы читаете вопрос: Лемма накачки для обычного языка - person Grijesh Chauhan schedule 07.04.2014