Построение грамматик (задолбали заочники)

← →
Ozone © (2005-05-26 09:24) [0]

Добрый день.

Есть такая задачка:

Поездом наз-ся произвольная последовательность локомотивов и вагонов, начиная с локомотива. Построить грамматику для понятия <поезд>, считая, что понятия <локомотив> и <вагон> являются терминальными символами.

Помню еще года 2 назад что-то подобное делали на 2м курсе, но теории не осталось... Может ткнете пальцем в нужную статейку... Заранее благодарен.

← →
Ega23 © (2005-05-26 09:26) [1]

http://www.uni-dubna.ru/~mazny/kurses/index.html

← →
Юрий Зотов © (2005-05-26 09:42) [2]

<цепочка_вагонов> ::= <вагон> | <вагон> <цепочка_вагонов>
<поезд> ::= <локомотив> <цепочка вагонов>

← →
Ozone © (2005-05-26 09:52) [3]

> [1] Ega23 © (26.05.05 09:26)

Пасиб, поштдирую.

> [2] Юрий Зотов © (26.05.05 09:42)

Эт понятно :) Просто интересует то, как правильно это все должно быть оформлено на бумаге.

← →
Анонимщик1 (2005-05-26 11:05) [4]

Тогда цепочка
<локомотив><вагон><локомотив>
не будет поездом, а должна быть.
Правильно будет так:
<поезд> ::= <локомотив><цепочка вагонов>
<цепочка вагонов> ::= <вагон><цепочка вагонов>|<локомотив><цепочка вагонов>|<epsilon>

← →
КаПиБаРа © (2005-05-26 11:09) [5]

А есть еще цепочка локомотивов

← →
Ozone © (2005-05-26 11:11) [6]

> [5] КаПиБаРа © (26.05.05 11:09)

Это не противоречит условию, мне кажется.

← →
pasha_golub © (2005-05-26 12:01) [7]

КаПиБаРа © (26.05.05 11:09) [5]
Для такого случая, будем полагать что максимум цепочка может содержать два локомотива.

<локо_цепь> --> <локомотив> | <локомотив_бета>
<локомотив_бета --> <локомотив> | <e>
<цепочка вагонов> --> <вагон> | <вагон><цепочка вагонов> | <e>
<поезд> --> <локо_цепь><цепочка вагонов>

Вообщем, поупражнялись в остроумии... А теперь работать!!! :0)

Вот верный вариант :)

ПОЕЗД:

S1 -> "локомотив" S2
S2 -> "вагон" S2 | "локомотив" S2 | <empty>

Ozone © (26.05.05 12:22) [8]
Ни фига подобного. Проверь:

"локомотив" "вагон" "локомотив" "вагон"...

Грамматике удовлетворяет ;-)

← →
Анонимщик1 (2005-05-26 15:24) [10]

И что? И под грамматику ведь подходит, так что все верно.

Построение грамматик (задолбали заочники) Найти похожие ветки