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

Use the advantage of Options being in the form on RightLinear and directly convert the machine to RightLinear Reg Gram.

So option B matches

---

use reverse substitution of epsilon & check by counter examples

---

For exam approach, BEST ANSWER is sufficient but 

for proper analysis    Read this,

in 2nd line, u will find    F = { B }  ...............which means B is the final state  AND

                                      B → ϵ     ...............we include ϵ in the final state

 

From this observation, we can eliminate, opt. D

Now let's first see the Conversion Rule,

 

Suppose the DFA has transition

                                            δ ( P, a ) = Q        

Then the grammar production is

                                            P → aQ​

Notice the order carefully:

• input symbol first
• next state second

                               NOT     P → Qa

Now let's see options,

 

Option A writes

                               A →  aB     ....................which should be correctly written as  A → aA

for

                           δ( A, a ) = A

which is incorrect.

 

Option C writes

                                       A → bB  .....................which is OK 

for   

                                      σ(A,b) = B           

BUT  it also writes

                                     A → aB   .....................which is not OK 

WHY ?

Because,                     σ(A,a) = B  .............should be present in the Question but it is not.

Hence, incorrect.

Hence, correct Answer is Opt. (B) 

                         

Answer 1

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

Comments

nice ;)

---

a bit of explanation please

---

it comes under, regular grammar from FA

---

Can you please explain what is meant by K=VuΣ?

---

B->eps  ?

i have nt seen grammar which specify final state like that production??then what for initial state?

---

Can you please explain what is meant by K=VuΣ?

It says set of vertices can be union of states and input alphabets. Context sensitive grammar. But it doesn't matter here.

---

@Praveen Saini sir please explain bit more about B->eps  ?

---

Given that it's a FA.

so, grammer generates it is a regular grammer. then why V = K union sigma.

as per the rule of regular grammer lhs always contains variables

---

Regular expression: a*b(ba*b+a)* : given DFA accepts odd number of b's . inorder to generate the string 'b' by the grammar we added this production B-->Eps..so to control number of b's generated as per our requirement always an epsilon production is added for final state

---

Machine M accept b

But we can't generate b with option B

Please explain

---

A->bB is there so epsilon can be produced

---

L(M) = odd no. of b’s

Answer 2

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.

Comments

👍

---

@Abhrajyoti00

I think the reasoning you have given for $Option$  $A$ , $D$ and $C$ is incorrect.

Option A) {A→aB,A→bA,B→bA,B→aA,B→ϵ}

⟹A→aB/bA

B→bA/aA/ϵ          We can notice that this grammar forces strings to always end in b which is wrong.

 All the three options can generate  $“a”$  which is not generated by the Machine M.

Thus making Option B $True$ and rest $false$.

---

@Pranavpurkar Yes yes thanks Pranav. Corrected it now.

Answer 3

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.

Answer 4

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 5

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