Узнать сгенерированный язык, учитывая контекстно-свободную грамматику?

Должен ли я вручную применять продукционные правила, чтобы узнать язык, сгенерированный этой грамматикой? Это утомительно, есть ли какой-нибудь трюк/совет, чтобы ускорить процесс?

G = {{S, B}, {a, b}, P, S}
P = {S -> aSa | aBa, B -> bB | b}

EDIT: я нашел ответ Матахона хорошим, который думает о каждом языке, сгенерированном нетерминальным символом, а затем объединяет их.

Но я все еще застрял, когда мне нужно решить некоторые сложные примеры, подобные этому:

G = {{S, R, T}, {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, P, S}

P = {S -> A | AS | BR | CT,
     R -> AR | BT | C | CS,
     T -> AT | B | BS | CR,
     A -> 0 | 3 | 6 | 9,
     B -> 1 | 4 | 7,
     C -> 2 | 5 | 8}

Сумасшедший, не так ли? Взято из прошлых экзаменов (курс языков программирования).


recursion grammar context-free-grammar
person gremo    schedule 24.01.2011    source источник
comment
Являются ли запятые частью алфавита этого языка?   -  person David Weiser    schedule 24.01.2011
comment
@Matajon нет, это моя проблема. Я отредактировал текст, чтобы исправить неправильное определение. Спасибо.   -  person gremo    schedule 24.01.2011

Ответы (2)


arrow_upward
2
arrow_downward

Я не знаю какой-либо общей хитрости, но обычно полезно подумать о языке, сгенерированном каждым нетерминалом.

В вашем примере язык, сгенерированный из B, очевидно, L(B) = {b}^+. Затем вы думаете о правилах S, используя первое правило, вы можете генерировать сентенциальные формы {a^n.S.a^n | n >= 1}. Если вы используете второе правило для этих форм предложений или только для S, вы можете создавать формы предложений {a^n.B.a^n | n >= 1}.

Отдых довольно прост, вы объединяете эти две вещи и получаете L(G) = {a^n.b^+.a^n | n >= 1}

Кстати, в определении грамматики терминалы и нетерминалы — это множества, а не кортежи. И третий компонент — правила производства, а не начальный символ. Поэтому вы должны написать G = {{S, B}, {a, b}, P, S}.

Изменить

На самом деле, есть способ решить ваш второй пример, не задумываясь, просто следуя чему-то вроде поваренной книги. Потому что язык, созданный вашей второй контекстно-свободной грамматикой, на самом деле является регулярным.

Когда вы заменяете правила для A, B и C на первые три правила, вы получаете

P' = {S -> 0 | 3 | 6 | 9 | 0S | 3S | 6S | 9S | 1R | 4R | 7R | 2T | 5T | 8T
     R -> 0R | 3R | 6R | 9R | 1T | 4T | 7T | 2 | 5 | 8 | 2S | 5S | 8S
     T -> 0T | 3T | 6T | 9T | 1 | 4 | 7 | 1S | 4S | 7S | 2R | 5R | 8R}

А P' — это обычная грамматика. Из-за этого вы можете преобразовать его в недетерминированный конечный автомат (есть очень простой способ, ищите его), а затем преобразовать полученный NFA в регулярное выражение (это не так просто, но если вы будете следовать алгоритму и не заблудитесь , вы должны быть в порядке). И по регулярному выражению легко сказать, какой язык оно описывает.

Кроме того, когда у вас есть NFA для этого языка, вы можете посмотреть на него и определить, что он делает логически (это как-то связано с количеством 1,4,7 и 2,5,8 в слове и mod 3 их различия. Подумайте хорошенько, это ваша домашняя работа, после всего :-) )

Конечно, если вы не используете контекстно-свободную грамматику, генерирующую обычный язык, вы не сможете использовать этот прием. Нет общего способа сказать, какой язык генерирует грамматика (проблема языкового равенства для CFG неразрешима), вы должны думать о каждом отдельном примере и искать сходства и закономерности в его логической структуре.

person Martin Jonáš    schedule 24.01.2011
comment
Хороший совет. Очень помогает, но как насчет более сложных примеров? (см. мои правки). Спасибо. - person gremo; 25.01.2011
comment
Отличное объяснение. Я только что нашел способ представить грамматику в виде NFA, это довольно просто, как вы сказали. Однако я все еще ищу хорошую отправную точку для изучения второго прохода (регулярное выражение). Можете ли вы указать мне правильное направление? Кстати ответ принят! - person gremo; 25.01.2011

arrow_upward
0
arrow_downward

Я думаю, вам просто нужно применить правила производства.

person David Weiser    schedule 24.01.2011