retagged by
3,170 views
20 votes
20 votes

Is the language generated by the grammar $G$ regular? If so, give a regular expression for it, else prove otherwise

  • G:    
    • $S \rightarrow aB$
    • $B \rightarrow bC$
    • $C \rightarrow xB$
    • $C \rightarrow c$
retagged by

2 Answers

Best answer
37 votes
37 votes

First of all this grammar is right linear. And we know:

Two special types of linear grammars are the following:

  • the left-linear or left regular grammars, in which all nonterminals in right hand sides are at the left ends;
  • the right-linear or right regular grammars, in which all nonterminals in right hand sides are at the right ends.

Hence the given grammar is regular and hence the language generated by regular grammar will also be regular. Alternatively we can also write a regular expression for it. Let us see how to do it:

Given grammar:

$G:$   $S\rightarrow aB$

        $B \rightarrow bC$

        $C\rightarrow xB \mid c$

So, we can reverse substitution from $C$ onwards to $S$ to see what $S$ generates..

Substituting the yield of $C$ in $B$, we have:

      $B \rightarrow bxB \mid bc$

     which gives $B = (bx)^* bc$

Now, substituting $B$ in $S$ we have:

     $\mathbf{S \rightarrow aB}$

     $\mathbf{S  =  a(bx)^*bc}$

Hence, the corresponding regular expression is :  $\mathbf{a(bx)^*bc}$

edited by
7 votes
7 votes

         S→aB

        B→bC

        C→xB

        C→c

given grammar is right linear

 it is better to draw m/c after that u can easily write the regular expression

now u can see that 

regular expn is :     a(bx)*bc

Related questions

20 votes
20 votes
3 answers
1
makhdoom ghaya asked Nov 22, 2016
9,032 views
Let $R_{1}$ and $R_{2}$ be regular sets defined over the alphabet $\Sigma$ Then:$R_{1} \cap R_{2}$ is not regular.$R_{1} \cup R_{2}$ is regular.$\Sigma^{*}-R_{1}$ is regu...
9 votes
9 votes
2 answers
3
makhdoom ghaya asked Nov 26, 2016
1,918 views
Show that the elements of the lattice $(N, \leq)$, where $N$ is the set of positive intergers and $a \leq b$ if and only if $a$ divides $b$, satisfy the distributive prop...
0 votes
0 votes
0 answers
4