Грамматика регулярного выражения

Каковы шаги процедуры, чтобы найти регулярное выражение, которое принимает тот же язык данной грамматики?

  • S --> b | AA
  • А --> аА | Абб | ϵ

regular-language left-recursion context-free-grammar automata-theory
person Whando    schedule 29.01.2014    source источник
comment
Я думаю, вам придется более подробно объяснить, что вы пытаетесь сделать, если хотите получить ответ. И что вы пробовали? Что у вас не работает? Вам нужно проявить некоторое усилие с вашей стороны. Никто не будет просто писать ваш код за вас.   -  person Bryan Elliott    schedule 29.01.2014
comment
Это не вопрос программирования, а скорее информатика: cs.stackchange.com.   -  person Kaz    schedule 29.01.2014
comment
Пожалуйста, не используйте ответы как вопросы. Вы можете отредактировать эту информацию в своем вопросе.   -  person Toon Krijthe    schedule 19.03.2014

Ответы (2)


arrow_upward
2
arrow_downward

Я пишу что-то, чтобы попытаться понять (надеюсь, это поможет):

  1. Согласно S --> b, строка 'b' является строкой на языке грамматики.

  2. Используя продукцию A A --> aA | &, мы можем сгенерировать: " A, за которым следует любое количество a", или в RE: a*A (* из-за эпсилон)

  3. Точно так же, используя A ---> Abb | &, мы можем сгенерировать «любое количество bb, за которым следует A», или в RE: A(bb)* (* из-за эпсилон)

  4. Используя 2 и 3, используя A, вы можете сгенерировать: a*(bb)*

  5. Обратите внимание, что в конечном итоге переменная должна быть преобразована в терминал, поэтому A можно преобразовать в a, bb или &.

  6. Из 4, используя AA, мы можем сгенерировать: a*(bb)*a(bb)*.

Итак, в языке, порожденном грамматикой, b + a*(bb)*a(bb)*

Для процедуры прочитайте этот ответ: Построение эквивалентной регулярной грамматики из регулярного выражения Я объяснил от RE к грамматике, я чувствую, что ответ поможет вам лучше понять.

person Grijesh Chauhan    schedule 29.01.2014
comment
1.ОК 2.это любое количество букв s, за которыми следует буква А? 3.это A, за которым следует любое количество bb s? 4. Это будет A(bb)? 5.OK 6.OK Могу ли я начать работать с грамматикой G1, которая эквивалентна приведенной выше грамматике G без ϵ-произведений? Я имею в виду S --›b|AA|A ; A--›aA|Abb|a|bb . Какая самая лучшая и простая процедура? У вас есть документация по этим правилам, применимым к грамматике в вашем первом ответе? - person Whando; 30.01.2014
comment
@Whando сначала узнайте ответ, который я связал, тогда только я могу помочь. - person Grijesh Chauhan; 30.01.2014
comment
Я научился этому. Достаточно ли ваших опубликованных правил, чтобы найти решение (регулярное выражение) для любой грамматики? Могу ли я упростить грамматику, избегая ϵ-продукции, или это не рекомендуется? Спасибо - person Whando; 30.01.2014
comment
... ...) для любой регулярной (левой или правой) грамматики. - person Whando; 31.01.2014
comment
@ Whando Я могу ответить вам на выходных ... просто прочитайте этот связанный ответ и ответы, связанные с этим ответом. - person Grijesh Chauhan; 31.01.2014
comment
@Whando 2.*it's any number of a s followed by A?* , 3. it's A followed by any number of bb s? -- Это просто способ написания -- Но RE должен быть четким. Я думаю, что вы поняли. "Can I start to work with a grammar G1 that is equivalent at the grammar G above with no ϵ-productions?" Я не понял, что вы подразумеваете под этим, где G1? 4. It will be a*A(bb)* ? См., используя A, вы генерируете a*A или A(bb)*, чтобы преобразовать a*A(bb)* из сентенциальной формы в форму предложения, вы должны преобразовать A либо в a, либо в bb, либо в &, поэтому в конечном итоге вы получите a*(bb)* - person Grijesh Chauhan; 02.02.2014
comment
Грамматика G с продукцией: S --› b | АА; А --› аА | Абб | ϵ ----- Грамматика G1, сгенерированная G с применением удаления ϵ-произведений: S --› b | АА |А; А --› аА | Абб | а | bb ----- G1 порождают тот же язык, что и G, L(G1)= L(G)-ϵ - person Whando; 03.02.2014
comment
@ Whando да G1 и G являются эквивалентными грамматиками, обе генерируют один и тот же язык. - person Grijesh Chauhan; 03.02.2014

arrow_upward
0
arrow_downward

Грамматика:

  • S --> AS|a

  • A --> SA|b

    1. According to S --> a, string a is in language of grammar.
    2. Согласно A --> b, строка b находится на языке грамматики.
    3. Используя A --> SA, мы можем сгенерировать A-->SA ; А-->ССА ; А-->СССА ; ...
    4. Используя S --> AS, мы можем сгенерировать S --> AS; С-->ААС ; С-->АААС ; ...

Как я могу получить регулярное выражение, решение для этой грамматики?

Полезны ли эти правила?

  • x=yx+t решение y*t
  • x=xy+t решение ty*

S=AS+a;A=SA+b

S=A*a ; A=S*b

Из A=SA+b и S=AS+a

  • я получаю A=S*b и S=S*bS+a
  • поэтому я получаю S=(S*b)*a
  • S=(a*b)*a

Правильно @GrjeshChauhan ??

person Whando    schedule 30.01.2014
comment
According to A --> b, string b is in language of grammar., Нет, можно рассматривать только те строки на языке грамматики, которые можно сгенерировать с помощью S стартовой переменной. Конечно, 'b' можно сгенерировать с помощью A, но b не является частью языка грамматики. наименьшие строки в языке грамматики a. Второй наименьший может быть либо ba, либо bb. - person Grijesh Chauhan; 02.02.2014
comment
@GrjeshChauhan ... Я сделал ошибку, вы правы, поскольку строка «b» из нетерминала A не является частью языка, сгенерированного этой грамматикой с аксиомой S. --- Is S=(ab)* решение регулярного выражения, которое генерирует тот же язык этой грамматики? Сколько рекурсивных сентенциальных форм я должен сгенерировать, чтобы быть уверенным, что нашел правильное регулярное выражение? (например, S=Aa;A=Sb --- S=(Sb) *a --- S=((Aa)*b)*a --- S=(((Sb)*a)*b)*a . ) - person Whando; 03.02.2014