Леволинейные и правые линейные грамматики

Мне нужна помощь в построении леволинейной и правой линейной грамматики для языков ниже?

a) (0+1)*00(0+1)* b) 0*(1(0+1))* c) (((01+10)*11)*00)* 

Для a) у меня есть следующее:

 Left-linear S --> B00 | S11 B --> B0|B1|011 Right-linear S --> 00B | 11S B --> 0B|1B|0|1 

Это верно? Мне нужна помощь с b & c.

Построение эквивалентной регулярной грамматики из регулярного выражения

Во-первых, я начинаю с некоторых простых правил для создания регулярной грамматики (RG) из регулярного выражения (RE).
Я пишу правила для правильной линейной грамматики (оставляя в качестве упражнения для написания аналогичных правил для левой линейной грамматики)

ПРИМЕЧАНИЕ. Заглавные буквы используются для переменных и для терминалов в грамматике. Символ NULL – ^ . Термин «любое число» означает ноль или более раз, что означает «закрытие звезды».

[ ОСНОВНАЯ ИДЕЯ ]

  • ОДИНОЧНЫЙ ТЕРМИНАЛ: Если RE просто e (e being any terminal) , мы можем написать G , причем только одно производственное правило S --> e (где S is the start symbol ), является эквивалентным RG.

  • UNION OPERATION: Если RE имеет вид e + f , где оба e and f are terminals , мы можем написать G с двумя производственными правилами S --> e | f S --> e | f , является эквивалентным RG.

  • CONCATENATION: Если RE имеет вид ef , где оба e and f are terminals , мы можем написать G , причем два правила производства S --> eA, A --> f , являются эквивалентными RG.

  • ЗАКРЫТИЕ ЗВЕЗДЫ: Если RE имеет вид e* , где e is a terminal операция * Kleene star closure и * Kleene star closure , мы можем написать два правила производства в G , S --> eS | ^ S --> eS | ^ , является эквивалентным RG.

  • PLUS CLOSURE: Если RE имеет вид e + , где e is a terminal операция e is a terminal и + Kleene plus closure , мы можем написать два правила производства в G , S --> eS | e S --> eS | e , является эквивалентным RG.

  • STAR CLOSURE ON UNION: Если RE имеет вид (e + f) *, где оба e and f are terminals , мы можем написать три правила производства в G , S --> eS | fS | ^ S --> eS | fS | ^ S --> eS | fS | ^ , является эквивалентным RG.

  • PLUS CLOSURE ON UNION: Если RE имеет вид (e + f) + , где оба e and f are terminals , мы можем написать четыре правила производства в G , S --> eS | fS | e | f S --> eS | fS | e | f S --> eS | fS | e | f , является эквивалентным RG.

  • ЗАКРЫТИЕ ЗВЕЗДЫ НА КОНКАТЕНЦИЮ: Если RE имеет вид (ef) *, где оба e and f are terminals , мы можем написать три правила производства в G , S --> eA | ^, A --> fS S --> eA | ^, A --> fS , является эквивалентным RG.

  • PLUS CLOSURE ON CONCATENATION: Если RE имеет вид (ef) + , где оба e and f are terminals , мы можем написать три правила производства в G , S --> eA, A --> fS | f S --> eA, A --> fS | f , является эквивалентным RG.

Убедитесь, что вы понимаете все вышеприведенные правила, вот сводная таблица:

 +-------------------------------+--------------------+------------------------+ | TYPE | REGULAR-EXPRESSION | RIGHT-LINEAR-GRAMMAR | +-------------------------------+--------------------+------------------------+ | SINGLE TERMINAL | e | S --> e | | UNION OPERATION | e + f | S --> e | f | | CONCATENATION | ef | S --> eA, A --> f | | STAR CLOSURE | e* | S --> eS | ^ | | PLUS CLOSURE | e+ | S --> eS | e | | STAR CLOSURE ON UNION | (e + f)* | S --> eS | fS | ^ | | PLUS CLOSURE ON UNION | (e + f)+ | S --> eS | fS | e | f | | STAR CLOSURE ON CONCATENATION | (ef)* | S --> eA | ^, A --> fS | | PLUS CLOSURE ON CONCATENATION | (ef)+ | S --> eA, A --> fS | f | +-------------------------------+--------------------+------------------------+ 

примечание: символ e и f – терминалы, ^ – символ NULL, а S – стартовая переменная

[ОТВЕТ]

Теперь мы можем решить вашу проблему.

a) (0+1)*00(0+1)*

Описание языка: все строки состоят из 0s и 1s, содержащих по меньшей мере одну пару 00 .

  • Правая линейная грамматика:

    S -> 0S | 1S | 00A
    A -> 0A | 1A | ^

    Строка может начинаться с любой строки из 0 с и 1 с, поэтому включены правила s --> 0S | 1S s --> 0S | 1S и поскольку по крайней мере одна пара 00 не имеет нулевого символа. S --> 00A потому что 0 , 1 может быть после 00 . Символ A заботится о 0 и 1 после 00 .

  • Левая линейная грамматика:

    S -> S0 | S1 | A00
    A -> A0 | A1 | ^

b) 0*(1(0+1))*

Описание языка: Любое число из 0, за каждым числом 10 и 11.
{потому что 1 (0 + 1) = 10 + 11}

  • Правая линейная грамматика:

    S -> 0S | A | ^
    A -> 1B
    B -> 0A | 1A | 0 | 1

    Строка начинается с любого числа 0 поэтому правило S --> 0S | ^ S --> 0S | ^ включены, тогда правило для генерации 10 и 11 для любого количества раз с использованием A --> 1B and B --> 0A | 1A | 0 | 1 A --> 1B and B --> 0A | 1A | 0 | 1 A --> 1B and B --> 0A | 1A | 0 | 1 .

    Другой альтернативной прямой линейной грамматикой может быть

    S -> 0S | A | ^
    A -> 10A | 11A | 10 | 11

  • Левая линейная грамматика:

    S -> A | ^
    A -> A10 | A11 | В
    B -> B0 | 0

    Альтернативной формой может быть

    S -> S10 | S11 | B | ^
    B -> B0 | 0

c) (((01+10)*11)*00)*

Описание языка: во- первых, язык содержит строку null (^), потому что там есть * (звезда) вне всякой вещи, присутствующей внутри (). Кроме того, если строка на языке не равна нулю, что вызывающе заканчивается на 00. Можно просто подумать об этом регулярном выражении в виде (((A) * B) * C) *, где (A) * есть (01 + 10) *, то есть любое число повторений 01 и 10. Если в строке есть экземпляр A, то B вызывающе, потому что (A) * B и B равно 11.
Некоторые примерные строки {^, 00, 0000, 000000, 1100, 111100, 1100111100, 011100, 101100, 01110000, 01101100, 0101011010101100, 101001110001101100 ….}

  • Левая линейная грамматика:

    S -> A00 | ^
    A -> B11 | S
    B -> B01 | B10 |

    S --> A00 | ^ S --> A00 | ^ потому что любая строка имеет значение null или если она не равна нулю, она заканчивается на 00 . Когда строка заканчивается на 00 , переменная A соответствует шаблону ((01 + 10)* + 11)* . Опять же, этот шаблон может быть нулевым или должен заканчиваться на 11 . Если его значение равно null, то A снова совпадает с S т. Е. Строка заканчивается шаблоном типа (00)* . Если шаблон не равен нулю, B соответствует (01 + 10)* . Когда B соответствует всем возможным, A снова начнет сопоставлять строку. Это закрывает крайний край * в ((01 + 10)* + 11)* .

  • Правая линейная грамматика:

    S -> A | 00S | ^
    A -> 01A | 10A | 11S

Вторая часть вопроса :

 For a) I have the following: Left-linear S --> B00 | S11 B --> B0|B1|011 Right-linear S --> 00B | 11S B --> 0B|1B|0|1 

( ответ )
Вы ошибаетесь по следующим причинам:

Левая линейная грамматика неверна, потому что строка 0010 невозможно сгенерировать. Правильная линейная грамматика неверна, потому что строка 1000 невозможно создать. Хотя оба языка написаны на основе регулярного выражения вопроса (а).

РЕДАКТИРОВАТЬ
Добавление DFA для каждого регулярного выражения. так что можно найти его полезным.

a) (0+1)*00(0+1)*

DFA

b) 0*(1(0+1))*

DFA

c) (((01+10)*11)*00)*

Рисование DFA для этого регулярного выражения является трюком и сложным.
Для этого я хотел добавить DFA’s

Чтобы упростить задачу, мы должны думать, что форма RE RE для меня RE (((01+10)*11)*00)* выглядит как (a*b)*

 (((01+10)*11)* 00 )* ( a* b )* 

На самом деле в вышеприведенном выражении a оно само в виде (a*b)* что ((01+10)*11)*

RE (a*b)* равно (a + b)*b + ^ . DFA для (a b) – как belows:

DFA

DFA для ((01+10)*11)* :

DFA

DFA для (((01+10)*11)* 00 )* :

DFA

Попытайтесь найти сходство в построении выше трех DFA. не двигайтесь вперед, пока вы не поймете первый

Правила преобразования регулярных выражений в левую или правую линейную регулярную грамматику Чит-лист

Давайте будем гением компьютера.