edited by
6,831 views
46 votes
46 votes

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)$ ?

  1. $\{A → aB, A → bA, B → bA, B → aA, B → \epsilon)$
  2. $\{A → aA, A → bB, B → aB, B → bA, B → \epsilon)$
  3. $\{A → bB, A → aB, B → aA, B → bA, B → \epsilon)$
  4. $\{A → aA, A → bA, B → aB, B → bA, A → \epsilon)$
edited by

5 Answers

Best answer
65 votes
65 votes
$\sigma (A, a) = A,$           $A →aA$

$\sigma (A, b) = B,$           $A →bB$

$\sigma(B, a) = B $           $B →aB$

$\sigma(B, b) = A$            $B →bA$

$B$ is final state so   $B → \epsilon$

Correct Answer: $B$
edited by
7 votes
7 votes

Answer : Option B

Given: $\sigma(A, a) = A, \sigma(A, b) = B, \sigma(B, a) = B \text{ and}  \ \sigma(B, b) = A$

The DFA will be:-

Reg expression : $a^*b(a+ba^*b)^*$ ; The language accepted by the DFA is : All strings containing odd number of ‘$b$’

Now, let’s examine the options:-

Option A) $\{A → aB, A → bA, B → bA, B → aA, B → \epsilon\}$

$\implies A→ aB/bA$

$B→ bA/aA/ \epsilon$          We can notice that this grammar generates  “a” which is not generated by the Machine M. This is wrong.

 

Option C) $\{A → bB, A → aB, B → aA, B → bA, B → \epsilon\}$ 

$\implies A → bB/ aB$

$B → aA/bA/\epsilon$        We can notice that this grammar also generates  “a” which is not generated by the Machine M. This is wrong.

 

Option D) $\{A → aA, A → bA, B → aB, B → bA, A → \epsilon\}$

$\implies A → aA/bA/\epsilon$

$B → aB/bA$            We can notice that this grammar accepts null string which is not generated by the Machine M. Hence it is also wrong.

 

Option B) $\{A → aA, A → bB, B → aB, B → bA, B → \epsilon\}$

$\implies A → aA/bB$

$B → aB/bA/\epsilon$        We can notice that this grammar accepts only odd number of $b$ which is correct.

 

Edit: Provided the corect reasonings.

edited by
3 votes
3 votes
Draw the DFA for M. It will accept all strings containing an odd number of ‘b’ s. Grammars in options A, C and D can generate an even length string(eg: “abba” and Epsilon for option D). So the answer will be B.
2 votes
2 votes
Using the Elimination method,

In the given production, an odd number of b’s are selected while even number of b’s are restricted.

(A) False, because bba is accepted in the given grammar.

(C) False, because a is accepted in the given grammar.

(D) False, because a is accepted in the given grammar.

So, option (B) is correct answer.
Answer:

Related questions

28 votes
28 votes
5 answers
2
Ishrat Jahan asked Nov 1, 2014
8,780 views
Which one of the following regular expressions is NOT equivalent to the regular expression $(a + b + c)^*$?$(a^* + b^* + c^*)^*$$(a^*b^*c^*)^*$$((ab)^* + c^*)^*$$(a^*b^* ...