in Theory of Computation retagged by
2,315 views
19 votes
19 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$
in Theory of Computation retagged by
2.3k views

4 Comments

@Bikram sir

I m not getting by applying Arden's lemma -

B = Sa + Cx     ------------- (1)

C = Bb             ---------------(2)

F = Cc            ---------------(3)

Put (2) in (1) we get,

B = Sa + Bbx     // according to Arden's lemma, if R = Q + RP then R = QP*

Thus,

B = Sa(bx)*   -----------(4)

put (4) in (2)

C = Sa(bx)*b    ------------(5)

put (5) in (3)

F = Sa(bx)*b   ---------------(6)  // required expression

My question is - how eliminate S from (6)

pic by  

1
1
@kushagra $ab(xb)^*c$ This is also correct. right?
0
0
Yes, because b(xb)* = (bx)*b
0
0

2 Answers

35 votes
35 votes
Best answer

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

4 Comments

Yes it is as :  b(xb)* == (bx)*b which is one of the properties of regular expressions.
16
16

@ Habibkhan  thanks habib bhai.

2
2
For Right Linear Grammar we can draw a machine very easily and hence write reg exp very fast. Follow : https://gateoverflow.in/86864/gate-cse-1990-question-15a?show=327858#c327858
0
0
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

4 Comments

@pawan kumarln Can you tell how you write this RegEx? Using state elimination how we can write from your FA?

0
0

don't delete first and final state

if u delete state C

4
4
On eliminating B, i am getting ans as-

ab(xb)*c  so is it wrong?
0
0

It's right @codingo1234

1
1

Related questions