2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 Построение мп автомата
Сообщение27.10.2019, 10:27 


26/12/17
120
Хочу построить МП-автомат по КС-грамматике:
$S \to S1S$

$S \to S1S0S$

$S\to S1S0S0S$

Алгоритм построение МП-автомата по заданной КС-грамматике:
1) для каждого правила вывода $V \to y \in P$ определим $ \delta (q,\varepsilon,V)={(q,y)}$
2) для каждого терминала $a$ определим $\delta(q,a,a)={(q,\varepsilon)}$

С первым пунктом все ясно:
Добавляем $\delta(q,\varepsilon,S) = {(q,S1S),(q,S1S0S),,(q,S1S0S0S)}$.
Далее нужно добавить $\delta(q,0,0) = {(q,\varepsilon)}$ и $\delta(q,1,1) = {(q,\varepsilon)}$?

-- 27.10.2019, 11:40 --

Получается, что по такому алгоритму, мы можем выбрасывать из стека 0 и 1
$\delta(q,0,0) = {(q,\varepsilon)}$
$\delta(q,1,1) = {(q,\varepsilon)}$
Но до этого туда ничего не помещалось. Как это возможно?

 Профиль  
                  
 
 Re: Построение мп автомата
Сообщение27.10.2019, 13:38 
Заслуженный участник


27/04/09
28128
Так у вас там стартовый нетерминал $S$ не является одновременно маркером дна стека? (Должен бы, это явно входит в описание автомата, строимого по КС грамматике, у Хопкрофта.) А это ровно и значит, что он лежит в стеке в самом начале, оттуда всё и завертится.

NB: фигурные скобки набираются \{ \}, сами по себе они используются для группировки подвыражений.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 2 ] 

Модераторы: Модераторы Математики, Супермодераторы



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

Сейчас этот форум просматривают: B@R5uk


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group