语法的形式语言

Question

我试图从这些语法中推断出他们的语言：

对于第一个，我认为（但不确定）语言是： {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

为了达到第一个文法的形式语言，我尝试了多次不同形式的切割，发现'a'必然重复偶数次。

Answer 1

For the first one, i think (but not quiet sure) the language is: {a^(i)b^(j) | i mod 2 = 0 and j > 0}

反例：aab在该语言中，但不在语法语言中。

旁白：而不是

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

我觉得比较通俗的说法

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

for the second one, i don't have a single clue.

源自 S 的语言只是源自 A 和 B 的语言的串联。

A 有 2 个选项，一个是递归的，一个不是- 递归生产。由此，您应该能够获得源自 A.

的语言

与 B 类似，然后将它们连接起来。

语法的形式语言

The formal language of grammar

grammar

automation

formal-languages