Формальный язык грамматики - PullRequest
Новая
       15

Формальный язык грамматики

0 голосов
/ 26 января 2019

Я пытался вывести из этих грамматик их язык:

Во-первых, я думаю (но не совсем уверен), что язык: {a ^ (i) b ^ (j) | i mod 2 = 0 и j> 0}

а для второго у меня нет ни единой подсказки. 

1.
    G = ({S,A,B},{a,b},S,P) 
    P:
    S -> AAB
    A -> aaA | aa
    B -> bB | b

2.
    G = ({S,A,B},{a,b},S,P)
    P:
    S -> AB
    A -> aAb | epsilon
    B -> bBa | epsilon

Чтобы достичь формального языка первой грамматики, я попытался сократить его несколько раз в разных формах и увидел, что «а» обязательно повторяется четное число раз.

1 Ответ

0 голосов
/ 29 января 2019

Для первого, я думаю (но не совсем уверен), язык: {a ^ (i) b ^ (j) |i mod 2 = 0 и j> 0}

Контрпример: aab на этом языке, но не на языке грамматики.

В стороне: вместо 

{a^(i) ... | i mod 2 = 0 ...}`

Я думаю, что более распространено сказать 

{a^(2i) ... | ...}

для второго, у меня нет единой подсказки.

язык, производный от S, представляет собой просто конкатенацию языков, производных от A и B.

A, имеет 2 варианта, один рекурсивный, а другой - нет, поэтому любое предложение, полученное из Aрезультаты k> = 0 приложений рекурсивного производства с последующим однократным применением нерекурсивного производства.Исходя из этого, вы сможете получить язык, полученный из A.

Аналогично для B, а затем объединить их.

...