Подсобите с МП-автоматом для s-грамматики

Здесь Вы можете найти или обсудить множество различных алгоритмов, их описаний, реализаций на VB и других языках.
Zenitchik
Постоялец
Постоялец
 
Сообщения: 369
Зарегистрирован: 21.12.2006 (Чт) 14:48

Подсобите с МП-автоматом для s-грамматики

Сообщение Zenitchik » 15.02.2009 (Вс) 22:23

Грамматика такая
S - начальный нетерминал (он же единственный)
a, l, f, s, e - терминальные символы
null - пустая строка (лениво код эпсилона искать).

Продукции:
S::=aS
S::=lS
S::=fS
S::=sSeS
S::=null

Не могу составить таблицу переходов. Правило S::=null - мешает жить.
Либо я дурак, либо это не s-грамматика. Но чую, что исправить ситуацию можно каким-то небольшим преобразованием.
Знание английского языка - затрудняет понимание кода

tyomitch
Пользователь #1352
Пользователь #1352
Аватара пользователя
 
Сообщения: 12822
Зарегистрирован: 20.10.2002 (Вс) 17:02
Откуда: חיפה

Re: Подсобите с МП-автоматом для s-грамматики

Сообщение tyomitch » 15.02.2009 (Вс) 23:23

Если я ещё хоть что-то помню...
Код: Выделить всё
   {a,l,f},γ   s,γ    e,1   e,∅     ∅,1   ∅,∅
Q0   Q0,γ     Q0,γ1  Q0,   reject reject accept

Где:
Q0 -- единственное состояние
γ -- верхний символ магазина
1 -- единственный символ алфавита магазина
∅ -- признак конца ввода/магазина
Изображение


Вернуться в Алгоритмы

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 5

    TopList