найти контекстную грамматику для следующего языка - PullRequest
Новая
       22

найти контекстную грамматику для следующего языка

0 голосов
/ 17 июня 2019

Найти не зависящую от контекста грамматику для следующего языка (с n≥0 и m≥0): L = {w∈ {a, b} *: n_a ≠ n_b}

Предположим: n_a = n_b
S-> SS |aSb |bSa |λ

Добавить a или добавить b s-> SS |aSb |bSa |АС |BS |а |б

1 Ответ

1 голос
/ 17 июня 2019

Если число a отличается от числа b, то либо больше a, либо больше b.Мы можем обрабатывать эти случаи отдельно.Давайте разберемся с делом более первым.Чтобы убедиться, что есть больше, чем b, мы можем начать с равного числа a и b и внести некоторые изменения. 

S -> e | Sab | Sba | aSb | bSa | abS | baS

Это должна быть грамматика, которая дает нам в точности строки с одинаковым числома и б.Почему я так думаю?Он охватывает все способы добавления одного a и одного b за раз, так что это, вероятно, работает.Упражнение: докажите это.

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

S -> A | ASAaAbA | ASAbAaA | AaASAbA | AbASAaA | AaAbASA | AbAaASA
A -> Aa | a

Мы можем сделать то же самое для случая большего числа B: 

S -> B | BSBaBbB | BSBbBaB | BaBSBbB | BbBSBaB | BaBbBSB | BbBaBSB
B -> Bb | b

Получить ответ сейчас так же просто, как объединить: 

S -> A | ASAaAbA | ASAbAaA | AaASAbA | AbASAaA | AaAbASA | AbAaASA
S -> B | BSBaBbB | BSBbBaB | BaBSBbB | BbBSBaB | BaBbBSB | BbBaBSB
A -> a | Aa
B -> b | Bb

РЕДАКТИРОВАТЬ - как указал Велбог в комментариях, в нем пропущены некоторые строки, потому что A и B не получают a *и b *, но a + и b +, поэтому мы заставляем добавлять больше a и b, чем нам нужно в некоторых случаях.Возможно, менее чем ужасный способ решить эту проблему - изменить A и B, чтобы получить a * и b *, а затем просто вставить a и b вместе с A и B точно на один из A и B в каждом производстве.Это приведет к тому, что будет по крайней мере еще один a / b, и позволит произвольно больше, не требуя нескольких дополнительных экземпляров, как это делает приведенная выше грамматика.Итак: 

S -> Aa | AaSAaAbA | AaSAbAaA | AaaASAbA | AabASAaA | AaaAbASA | AabAaASA
        | ASAaaAbA | ASAabAaA | AaAaSAbA | AbAaSAaA | AaAabASA | AbAaaASA
        | ASAaAabA | ASAbAaaA | AaASAabA | AbASAaaA | AaAbAaSA | AbAaAaSA
        | ASAaAbAa | ASAbAaAa | AaASAbAa | AbASAaAa | AaAbASAa | AbAaASAa
S -> Bb | BbSBaBbB | BbSBbBaB | BbaBSBbB | BbbBSBaB | BbaBbBSB | BbbBaBSB
        | BSBbaBbB | BSBbbBaB | BaBbSBbB | BbBbSBaB | BaBbbBSB | BbBbaBSB
        | BSBaBbbB | BSBbBbaB | BaBSBbbB | BbBSBbaB | BaBbBbSB | BbBaBbSB
        | BSBaBbBb | BSBbBaBb | BaBSBbBb | BbBSBaBb | BaBbBSBb | BbBaBSBb
A -> e | Aa
B -> e | Bb

Некоторые из этих произведений, вероятно, не нужны, но грамматика должна работать.

...