Search code examples
automationgrammarformal-languages

The formal language of grammar


I'v tried to deduce from these grammars their language:

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

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

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

To reach the formal language of the first grammar, I tried to cut it several times in different forms and saw that 'a' necessarily repeated an even number of times.


Solution

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

    Counterexample: aab is in that language, but not in the language of the grammar.

    Aside: rather than

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

    I think it's more common to say

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

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

    The language derived from S is just the concatenation of the languages derived from A and B.

    A has 2 alternatives, one recursive and one not, so any sentence derived from A results from k>=0 applications of the recursive production, followed by a single application of the non-recursive production. From that, you should be able to get the language derived from A.

    Similarly for B, then concatenate them.