GATE CSE 1990 | Question: 15a

Question

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$

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  pawan kumarln

---

@kushagra $ab(xb)^*c$ This is also correct. right?

---

Yes, because b(xb)* = (bx)*b

Answer 1

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}$

Comments

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

---

@ Habibkhan  thanks habib bhai.

---

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

Answer 2

         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 expⁿ is :     a(bx)*bc

Comments

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

---

don't delete first and final state

if u delete state C

---

On eliminating B, i am getting ans as-

ab(xb)*c  so is it wrong?

---

It's right @codingo1234