GATE Overflow Test Series | Mock GATE | Test 4 | Question: 61

Question

Which of the following is/are regular grammar for the given finite automata? (Mark all the appropriate choices)

• A. $S_{1} \rightarrow aS_{2} \\
  S_{2} \rightarrow a S_{2} \mid bS_{2}$
• B. $S_{1} \rightarrow aS_{2} \\
  S_{2} \rightarrow a S_{2} \mid bS_{2} \mid \varepsilon$
• C. $S_{1} \rightarrow S_{2} a \\
  S_{2} \rightarrow S_{2} a \mid S_{2} b \mid \varepsilon$
• D. $S_{1} \rightarrow S_{1} a \mid S_{1} b \mid S_{2} a \\
  S_{2} \rightarrow \varepsilon$

Answer 1

Option $(B)$ is right linear grammar and option $(D)$ is left linear grammar.

$\textbf{PS1:}\; \underbrace{FA}_{L} \rightarrow \underbrace{RLG}_{L} \overset{R}{\rightarrow} \underbrace{LLG}_{L^{R}}$

$\textbf{PS2:}\; \underbrace{FA}_{L} \overset{R}\rightarrow \underbrace{FA}_{L^{R}} \rightarrow \underbrace{RLG}_{L^{R}} \overset{R}{\rightarrow} \underbrace{LLG}_{(L^{R})^{R} = L}$

Option A is wrong as the production is not terminating. Option C is not generating any string ending in $"b".$

So, the correct answer is $B;D.$

Comments

The state names are changed in option D. Instead of S1 it is S2 and instead of S2 it is S1. We only get option D after converting the RLG to LLG and reversing the state names. We only have to give the answer according to the given automata right?