Formal Languages and Automata

[Apprentice123]

How to find the grammar that generates the following languages

1) L1 = {a^{n+2} b^n | n >= 0};
2) L2 = {c a^n b^n | n>= 0};

My attempt

1)
S -> a
S -> aaSb
G1 = ( {S}, {a,b}, P, S )

2)
S -> aSb
S -> cE
G2 = ( {S}, {a,b,c},P,S )

*E is empty

Are is correct ?

[bobdark]

Aww so sorry but no they aaren't correct.
1)With the ule S->aaSb you'll derive 2 a's and 1 b per rules activation. So you'll get like 2n a's and n b's.The idea is to use the Grammar for (a^n)(b^n) and modify it by adding some variable that will derive the additional 2 a's.
Ill give you the basic grammar and you go ahead and try to modify it.
Grammar for {a^nb^n|n>=0}:
S->aSb|epsilon

2) your solution isn't correct here too, because the language is (im rephrasing): all the words that start with c, after c follow n a's and then n b's. In your solution 'c' can only be in the middle of the word, or as the whole word, because S derives a and b around itself in the recursive rule, and E doesn't derive anything that follows 'c'. But the rule S->cE is in the right direction - thats what I meant in 1), by saying add an additional variable that will derive the additional (to the a^nb^n format) part. Here S fullfills its role and what you got left is to define E to derive a^nb^n and work's done (and get rid of the S->aSb rule in this case).

[Apprentice123]

Aww so sorry but no they aaren't correct.
1)With the ule S->aaSb you'll derive 2 a's and 1 b per rules activation. So you'll get like 2n a's and n b's.The idea is to use the Grammar for (a^n)(b^n) and modify it by adding some variable that will derive the additional 2 a's.
Ill give you the basic grammar and you go ahead and try to modify it.
Grammar for {a^nb^n|n>=0}:
S->aSb|epsilon

2) your solution isn't correct here too, because the language is (im rephrasing): all the words that start with c, after c follow n a's and then n b's. In your solution 'c' can only be in the middle of the word, or as the whole word, because S derives a and b around itself in the recursive rule, and E doesn't derive anything that follows 'c'. But the rule S->cE is in the right direction - thats what I meant in 1), by saying add an additional variable that will derive the additional (to the a^nb^n format) part. Here S fullfills its role and what you got left is to define E to derive a^nb^n and work's done (and get rid of the S->aSb rule in this case).

1) I do not understand, if S -> aaSb | E
The smallest word is not empty is:
S -> aaSb -> aab Is not a^n+2 b^n ????


2) I could not understand this

[bobdark]

1) yes but thats the only word that will be in the wanted language (in case S indeed also derives E, which you did not pecify at first). But say we want the next word: a^7b^5. Since S->aaSb is the only rule that derives b, you will have to apply it 5 times since 5 is the number of b's we want. Now the number of a's you'll get is 2*5 = 10 instead of 7.

2) lets say we want to derive the next word : "cab".
lets break it into cases (hell I feel as if im proving something in homework) regarding the which rule you apply first:
1) S-> cE ===> this means your word will be "c" because E doesn't derive anything.
2) S->aSb ===> lets say you apply this rule 'x' times (x>=1) and then apply S->cE. The derivation looks like: S ->(x times) a^xSb^x -> a^xcEb^x->a^xcb^x. Your word will be:
a^xcb^x - but c is in the middle of the word!

[Apprentice123]

1) yes but thats the only word that will be in the wanted language (in case S indeed also derives E, which you did not pecify at first). But say we want the next word: a^7b^5. Since S->aaSb is the only rule that derives b, you will have to apply it 5 times since 5 is the number of b's we want. Now the number of a's you'll get is 2*5 = 10 instead of 7.

2) lets say we want to derive the next word : "cab".
lets break it into cases (hell I feel as if im proving something in homework) regarding the which rule you apply first:
1) S-> cE ===> this means your word will be "c" because E doesn't derive anything.
2) S->aSb ===> lets say you apply this rule 'x' times (x>=1) and then apply S->cE. The derivation looks like: S ->(x times) a^xSb^x -> a^xcEb^x->a^xcb^x. Your word will be:
a^xcb^x - but c is in the middle of the word!

So I have to have three rules of derivation?
1)
S -> aaSb
S -> a
S -> E

2)
S -> aSb
S -> cS
S -> E

?

[bobdark]

1)Same problem. When you derive some number of b's you'll derive a double number of a's.

S->AAS'
S'->aS'b | epsilon
A->a
Thats is the solution. S' derives the a^nb^n word while S also makes sure there are 2 more a's in the beginning.

2) Wrong becase you allow more than 1 c in a word and you allow c's in the middle of a word.
Solution goes Same as above:

S->cS'
S'->aS'b|epsilon

S' derives a^nb^n and S makes sure there is exactly one c in the beginning.

[Apprentice123]

1)Same problem. When you derive some number of b's you'll derive a double number of a's.

S->AAS'
S'->aS'b | epsilon
A->a
Thats is the solution. S' derives the a^nb^n word while S also makes sure there are 2 more a's in the beginning.

2) Wrong becase you allow more than 1 c in a word and you allow c's in the middle of a word.
Solution goes Same as above:

S->cS'
S'->aS'b|epsilon

S' derives a^nb^n and S makes sure there is exactly one c in the beginning.

Thank you. But if I in problem 2 begin to:
S -> aSb -> acSb -> acb
c remained in the middle

[bobdark]

you misunderstood my solution. S derives cS'. S' is a variable different from S.
It can be rewritten as:
S->cE
E->aEb|epsilon

[Apprentice123]

you misunderstood my solution. S derives cS'. S' is a variable different from S.
It can be rewritten as:
S->cE
E->aEb|epsilon

Ah Yes thank you.
The grammar is
1)
G = ( {S,A,B}, {a,b}, P, S)
B -> AAS
S -> aSb | epsilon
A -> a

2)
G = ( {S,A}, {a,b,c}, P, S )
S -> cA
A -> aAb | epsilon

Ok ?

[bobdark]

1)
G = ( {S,A,B}, {a,b}, P, S)
B -> AAS
S -> aSb | epsilon
A -> a

G = ( {S,A,B}, {a,b}, P, B) - B should be the starting variable.