Интересный вопрос.

[thesz]

Можно ли задать регулярной грамматикой распознавание строки состоящей из четного количества единиц и нечетного нулей? Конечным автоматом без памяти - можно, говорят. И насколько задание этого распознавателя регулярной грамматикой будет сложнее по описанию, чем конечный автомат?

Comments

Проверим

[nealar]

У нас в конторе турник висит. Оной способности никогда не имел.

Re: Проверим

[thesz]

Подъем с переворотом учить все равно придется, однако это будет легче. ;)

[dtim]

Собственно, для любого КА можно построить эквивалентную регулярную грамматику. Классы языков, задаваемых регулярными грамматиками, конечными автоматами и регулярными выражениями, совпадают.

Но твоя грамматика меня что-то смущает. По-моему, в ней вообще нельзя вывести конечную цепочку: у тебя каждое правило заканчивается на нетерминал. (Кроме того, правила вида recognize ::= o1e0 в регулярной грамматике недопустимы).

Я бы написал так (e1e0 - начальный нетерминал):

e1e0 ::= '0' e1o0 | '1' o1e0 | '0'
e1o0 ::= '0' e1e0 | '1' o1o0
o1e0 ::= '0' o1o0 | '1' e1e0
o1o0 ::= '0' o1e0 | '1' e1o0 | '1'

Соответствующий автомат выглядит так (начальное состояние - e1e0, заключительное - e1o0, в строках - состояния, в столбцах - входы):

'0' '1'
e1e0 | e1o0 | o1e0
e1o0 | e1e0 | o1o0
o1e0 | o1o0 | e1e0
o1o0 | o1e0 | e1o0

Как-то так. Или я что-то путаю?

[dtim]

Форматирование сползло. В таблице автомата '0' относится ко второму столбцу, а '1' - к третьему.

А вот с турником у меня всегда были проблемы :(. :).

[thesz]

С грамматикой всё в порядке и с автоматом тоже. ;)

Хорошо, что у меня ошибки нашел, но я их исправлять не буду (там достаточно добавить эпсилон-правило в e1o0, и будет желанный останов, а стартовое правило должно быть e1e0). ;)

А что с турником-то? Как прошел - подтянулся, всех делов. ;)

[dtim]

А нет турника по пути. Был дома раньше, но об него все гости головой бились, пришлось снять :).