3

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 | ϵ
Grijesh Chauhan
  • 57,103
  • 20
  • 141
  • 208
Whando
  • 31
  • 1
  • 1
  • 3
  • 1
    I think you're going to have to explain more thoroughly what you're trying to do, if you want to get an answer.. Also what have you tried? What is not working for you? You need to show some effort on your part. No one is just going to write your code for you. – Bryan Elliott Jan 29 '14 at 18:13
  • This is not a programming question but rather computer science: http://cs.stackchange.com. – Kaz Jan 29 '14 at 18:51
  • Please do not use answers as questions. You can edit this information into your question. – Toon Krijthe Mar 19 '14 at 10:00

2 Answers2

2

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.

Community
  • 1
  • 1
Grijesh Chauhan
  • 57,103
  • 20
  • 141
  • 208
  • 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 a*A(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? – Whando Jan 30 '14 at 16:14
  • @Whando first learn the answer I linked then only I can help. – Grijesh Chauhan Jan 30 '14 at 17:14
  • 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 – Whando Jan 30 '14 at 17:23
  • ... ... )for any regular(left or right)grammar. – Whando Jan 31 '14 at 09:47
  • @Whando I can answer you @ weekend...just read this linked answer and answers linked to that answer. – Grijesh Chauhan Jan 31 '14 at 10:21
  • @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 Feb 02 '14 at 09:01
  • 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)-ϵ – Whando Feb 03 '14 at 08:37
  • @Whando yes G1 and G are equivalent grammars both generates same language. – Grijesh Chauhan Feb 03 '14 at 08:41
0

Grammar:

  • S --> AS|a

  • A --> SA|b

    1. According to S --> a, string a is in language of grammar.
    2. According to A --> b, string b is in language of grammar.
    3. Using A --> SA, we can generate A-->SA ; A-->SSA ; A-->SSSA ; ...
    4. Using S --> AS, we can generate S-->AS ; S-->AAS ; S-->AAAS ; ...

How can i reach the regular expression, solution for this grammar?

Are these rules useful?

  • x=yx+t the solution is y*t
  • x=xy+t the solution is ty*

S=AS+a;A=SA+b

S=A*a ; A=S*b

From A=SA+b and S=AS+a

  • i get A=S*b and S=S*bS+a
  • so i get S=(S*b)*a
  • S=(a*b)*a

Correct @GrijeshChauhan ??

Community
  • 1
  • 1
Whando
  • 31
  • 1
  • 1
  • 3
  • *`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`. – Grijesh Chauhan Feb 02 '14 at 09:06
  • @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=(a*b)*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=A*a;A=S*b --- S=(S*b)*a --- S=((A*a)*b)*a --- S=(((S*b)*a)*b)*a . ) – Whando Feb 03 '14 at 08:50