Grammar to Regular Expression

Question

Which is the procedure steps to find the regular expression that accept the same language of a given Grammar?

• S --> b | AA
• A --> aA | Abb | ϵ

Solution

I am writing something try to understand (hope it will help):

1. According to S --> b, string 'b' is a string in language of grammar.

2. Using A's productions A --> aA | & we can generate: " A followed by any number of as", or in RE: a*A (* because of epsilon)

3. Similarly, Using A ---> Abb | & we can generate "Any number of bbs followed by A", or in RE: A(bb)* (* because of epsilon)

4. Using 2 and 3 using A you can generate: a*(bb)*

5. Note ultimately a variable has to converted into terminal hence A can be convert into a, bb or &.

6. From 4, using AA we can generate: a*(bb)*a(bb)*.

So in language generated by grammar is b + a*(bb)*a(bb)*

For procedure read this answer : Constructing an equivalent Regular Grammar from a Regular Expression I explained from RE to grammar, I feel that answer will help you to understand better.

Comments

[Admin]

1.OK 2.it's any number of a s followed by A? 3.it's A followed by any number of bb s? 4.It will be aA(bb) ? 5.OK 6.OK Can I start to work with a grammar G1 that is equivalent at the grammar G above with no ϵ-productions? I mean S -->b|AA|A ; A-->aA|Abb|a|bb . Which is the best and easy procedure? Do you have some documentations for these rules apllied to the grammar in your first answer?

[Grijesh Chauhan]

@Whando first learn the answer I linked then only I can help.

[Admin]

I learnt it. It's enough your posted rules for find the solution(regular expression) for any grammar?. Can i simplify the grammar avoiding the ϵ-productions, or it's not advisable? thanks

[Admin]

... ... )for any regular(left or right)grammar.

[Grijesh Chauhan]

@Whando I can answer you @ weekend...just read this linked answer and answers linked to that answer.

[Grijesh Chauhan]

@Whando 2.*it's any number of a s followed by A?* , 3. it's A followed by any number of bb s? -- It is just way of writing -- But RE should be clear. I think that you understood. "Can I start to work with a grammar G1 that is equivalent at the grammar G above with no ϵ-productions?" I didn't understand what do you means by this where is G1? 4. It will be a*A(bb)* ? See using A you generate a*A or A(bb)* to convert a*A(bb)* from sentential to sentence form you have to convert A into either a or bb or & so ultimately you would have a*(bb)*

[Grijesh Chauhan]

According to A --> b, string b is in language of grammar., No, only those string in language of grammar can be consider those can be generated using S the start-variable. Of-course 'b' can be generated using A but b is not a part of language of Grammar. smallest strings in language of grammar is a. Second smallest can be either ba and bb.

[Admin]

Grammar G with productions: S --> b | AA; A --> aA | Abb | ϵ ----- Grammar G1 generated by G applying "remove ϵ-productions": S --> b | AA |A; A --> aA | Abb | a | bb ----- G1 generate the same language as G, L(G1)= L(G)-ϵ

[Grijesh Chauhan]

@Whando yes G1 and G are equivalent grammars both generates same language.

[Admin]

@GrijeshChauhan ...I made a mistake, you are right with string 'b' from nonterminal A isn't part of the language generated by this grammar with axiom S. ---Is S=(ab)*a the regular expression solution that generate the same language of this grammar? How many recursive sentential form I must generate for be sure that I found the correct regular expression?(e.g. S=Aa;A=Sb --- S=(Sb)*a --- S=((Aa)*b)*a --- S=(((Sb)*a)*b)*a . )