Grammar to Regular Expression

context-free-grammar regular-language left-recursion automata-theory
Whando picture Whando · Jan 29, 2014 · Viewed 11.5k times · Source

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 | ϵ

Answer

Grijesh Chauhan picture Grijesh Chauhan · Jan 29, 2014

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.

Related questions

Regular vs Context Free Grammars

I'm studying for my computing languages test, and there's one idea I'm having problems wrapping my head around. I understood that regular grammars are simpler and cannot contain ambiguity, but can't do a lot of tasks that are required for …

Read More
Context-free grammar for the language L = {a^(n)b^(m)c^(k): m = |i - k|}

I have this language L = {a^n b^m c^k: m = |n - k|}. I know m = |n - k| can be expressed in two ways 1) m = n - k for n >= k or n = m + k 2) m = …

Read More
Tips for creating "Context Free Grammar"

I am new to CFG's, Can someone give me tips in creating CFG that generates some language For example L = {am bn | m >= n} What I got is: So -> a | aSo | aS1 | e S1 -> b | …

Read More