Register

GO Classes DPP | GATE CS | Theory of Computation | State Variable Method

96 views
2 2 votes

Which of the following statements are correct for converting a finite automaton into an equivalent right-linear grammar?

  1. Each automaton state becomes a non-terminal.
     
  2. The start state becomes the start variable.
     
  3. A transition $p \xrightarrow{x} q$ becomes a production $P \to xQ$.
     
  4. If $q$ is a final state, then add $Q \to \epsilon$.
     
  5. Every non-final state must also get an $\epsilon$ production.

1 Answer

0 0 votes

The standard construction makes one grammar variable for each automaton state. 

The start state becomes the start variable. 

For each transition $p \xrightarrow{x} q$, we add the rule $P \to xQ$. 

If a state is final, the corresponding variable must be allowed to stop, so we add $Q \to \epsilon$. 

We do not add $\epsilon$ productions for non-final states because that would incorrectly accept strings ending there. 

Hence, A, B, C, and D are correct.

Voting & Accepting an answer helps improve the community
Answer:
← Previous · GO Classes DPP | GAT...Next → · GO Classes DPP | GAT...
← Previous in category · GO Classes DPP | GAT...Next in category → · GO Classes DPP | GAT...
Position:
Show:

Related questions

2 2 votes
1 1 answer
132
132 views
GO Classes asked Sep 5
132 views
GO Classes DPP | GATE CS | Theory of Computation | Terminal-only Rules
Consider the right-linear grammar,$$\begin{aligned}A &\to fB \mid gA \\B &\to gA \mid fC \mid f \\C &\to gA \mid fC \mid f\end{aligned}$$When this grammar is converted in...
2 2 votes
1 1 answer
88
88 views
GO Classes asked Sep 5
88 views
GO Classes DPP | GATE CS | Theory of Computation | NFA to Grammar
Consider the NFA given below: Which right-linear grammar is obtained by the standard NFA-to-grammar construction?$q_0 \to aq_1$,$q_1 \to aq_0 \mid bq_1 \mid \epsilon$ $q_...
1 1 vote
1 1 answer
104
104 views
GO Classes asked Sep 5
104 views
GO Classes DPP | GATE CS | Theory of Computation | Grammar to NFA
Consider the right-linear grammar,$$\begin{aligned}S &\to aB \mid bS \mid \epsilon \\B &\to aS \mid bB\end{aligned}$$Which NFA is obtained by the standard grammar-to-NFA ...
3 3 votes
1 1 answer
152
152 views
GO Classes asked Sep 5
152 views
GO Classes DPP | GATE CS | Theory of Computation | Grammar to NFA
Consider the right-linear grammar,$$\begin{aligned}S &\to aT \\T &\to abcS \mid b\end{aligned}$$If this grammar is converted into an NFA with one input symbol per transit...