GATE IT 2004 | Question: 41

Question

Let $M=(K, Σ, \sigma, s, F)$ be a finite state automaton, where

$K = \{A, B\}, Σ = \{a, b\}, s = A, F = \{B\},$
$\sigma(A, a) = A, \sigma(A, b) = B, \sigma(B, a) = B \text{ and}  \ \sigma(B, b) = A$

A grammar to generate the language accepted by $M$ can be specified as $G = (V, Σ, R, S), $ where $V = K \cup Σ$, and $S = A.$

Which one of the following set of rules will make $L(G) = L(M)$ ?

• A. $\{A → aB, A → bA, B → bA, B → aA, B → \epsilon)$
• B. $\{A → aA, A → bB, B → aB, B → bA, B → \epsilon)$
• C. $\{A → bB, A → aB, B → aA, B → bA, B → \epsilon)$
• D. $\{A → aA, A → bA, B → aB, B → bA, A → \epsilon)$

Comments

Strings ending with 'a' will also be accepted.

---

Sukhbir Singh Does the automata accept “aba”?

---

palashbehra5

Yes, it accepts aba , not because what @Sukhbir Singh said is correct, but because of the reasoning given by @Pritam Dutta.

Answer 1

We Can directly   make  Finite Automata  From  Given  Right Linear Grammar   Now Compare →

RLG  to  FA

RLG	FA
Start state     <-----------	----------->  $q_{0}$
Variable           <-----------	----------->    $Q$
Production Rules  <-----------	----------->   $\delta$

Now check only  B option is satisfying the conditions