GATE Overflow Test Series | Mock GATE | Test 1 | Question: 40

Question

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

• A. $S \rightarrow a \mid aA \mid bB \mid \varepsilon $
  $A \rightarrow aA \mid aS $
  $B \rightarrow cS \mid \varepsilon$
• B. $S \rightarrow a \mid b \mid aA \mid bB $
  $A \rightarrow a \mid aA \mid aS$
  $B \rightarrow c \mid cS\mid \varepsilon$
• C. $S \rightarrow a \mid aA \mid bB $
  $A \rightarrow aA \mid aS$
  $B \rightarrow cS \mid \varepsilon$
• D. $S \rightarrow a \mid b \mid aA \mid bB $
  $A \rightarrow a \mid aA \mid aS$
  $B \rightarrow a \mid cS \mid \varepsilon$

Answer 1

The easiest way to solve these kind of questions is to find the strings accepted by the given automata and not generated by the grammar in options or vice versa.

Option A: Generating empty string which is not accepted by the given automata.

Option C: Not generating $"bc"$ which is accepted by the given automata.

Option D: Generating $"ba"$ which is not accepted by the given automata.

Option B is the answer.

Comments

yes

---

Option B is generating string $aa$ which is not recognized by the given automata. @Deepak Poonia sir please comment on this.

---

@rexritz, $aa$ is accepted by the given automata. $S_1 \rightarrow_a A \rightarrow_a D. $