Да се напише пораждаща граматика и да се конструира автомат

[Гост]

Да се напише пораждаща граматика и да се конструира автомат,
разпознаващ пораждания език, ако

[ptj]

За да се конструира подобен автомат, той той трябва да може "да брои". Т.е. в процеса на работа на автомата разликата между броя на отварящите и затварящите скоби трябва да е естествено число, а финалното състояние трябва да нулира тази разлика.

Ще разгледаме само едно подмножество на дадения език, а именно [tex]L=\{(^k)^k\}[/tex]

Нека направим малък анализ:
1.) Заради взаимно еднозначното съответствие между автоматни граматики и автоматни езици може да разгледаме само крайни автомати.
2.) Има теорема, че всеки [tex]НДКА[/tex] може да се преобразува в [tex]ДКА[/tex]. Затова без загуба на общност може да считаме, че търсения от нас автомат е ДКА.
3.) Очевидно автомата няма да съдържа цикли, защото те не ни позволяват "да броим".
4.) Тогава за всяка нова отваряща скоба ще ни е необходимо ново състояние.
5.) Понеже нашия брояч може да бъде всяко произволно голямо естествено число, то броя на състоянията на автомата трябва да е неограничен.
6.) Намереното в 5.) противоречи на дефиницията, че автомата ни е "краен".

Това е.