Создайте DFA для следующего языка: L = {a ^ nb ^ n |п> = 1} - PullRequest
0 голосов
/ 04 февраля 2011

на языке n - это сила, но я не умел писать.

Ответы [ 2 ]

11 голосов
/ 04 февраля 2011

Я думаю, вы неправильно поняли свою домашнюю работу (не говоря уже о самих классах).Этот язык не является регулярным .Это означает, что вы не можете создать DFA для него.

Подумайте об этом: когда вы проходите цикл через a, вы нигде не держите количество выполненных вами операцийштат.У вас нет возможности узнать, сколько раз прочитать b.

Однако это можно сделать с помощью контекстно-свободной грамматики, подобной этой:

S->aSb|ab
0 голосов
/ 04 февраля 2011

Вы проходили лемму "Обычная накачка" в своем классе?

Аналогичная лемма прокачки существует и для языков Context Free

...