Consider the following language: \[ L = \{ w \in \{0,1\}^* \mid w \text{ ends with the substring } 011 \} \] Which one of the following deterministic finite automata accepts \(L\)?
Consider the following language: \[ L = \{ w \in \{0,1\}^* \mid w \text{ ends with the substring } 011 \} \] Which one of the following deterministic finite automata accepts \(L\)?
Show Hint
- A
- B
- C
- D
The Correct Option is D
Solution and Explanation
Step 1: Understanding the language.
The language \(L\) consists of all binary strings that end exactly with the substring \(011\). This means that the automaton must accept a string if and only if the last three symbols read are \(0, 1, 1\). Any extra input after reading \(011\) should cause rejection unless the suffix condition is re-established.
Step 2: Required DFA structure.
To recognize strings ending with \(011\), the DFA must:
• Track partial matches of the suffix \(011\)
• Correctly handle overlaps (for example, strings like \(0011\))
• Accept only when the input ends in state corresponding to full match of \(011\)
This typically requires four states:
• Start state (no match)
• State after reading \(0\)
• State after reading \(01\)
• Accepting state after reading \(011\)
Step 3: Evaluating the options.
• Option (A): Allows acceptance even if extra symbols follow \(011\) incorrectly, violating the "ends with" condition.
• Option (B): Has accepting state with self-loops on both \(0\) and \(1\), which accepts strings not ending in \(011\). Hence incorrect.
• Option (C): Incorrect transitions cause acceptance of strings that do not strictly end with \(011\).
• Option (D): Correctly tracks the suffix \(0 \rightarrow 01 \rightarrow 011\), and ensures acceptance only if the input terminates in the accepting state. It also correctly handles overlaps by redirecting transitions appropriately.
Step 4: Conclusion.
Only option (D) represents a deterministic finite automaton that accepts exactly the set of binary strings ending with the substring \(011\).
Top Questions on Regular expressions and finite automata
- Given a Context-Free Grammar \( G \) as follows: \[ S \to A a \ |\ b A c \ |\ d c \ |\ b d a \] \[ A \to d \] Which ONE of the following statements is TRUE?
- GATE CS - 2025
- Theory of Computation
- Regular expressions and finite automata
- Let \( \Sigma = \{1,2,3,4\} \). For \( x \in \Sigma^* \), let \( {prod}(x) \) be the product of symbols in \( x \) modulo 7. We take \( {prod}(\epsilon) = 1 \), where \( \epsilon \) is the null string. For example, \[ {prod}(124) = (1 \times 2 \times 4) \mod 7 = 1. \] Define \[ L = \{ x \in \Sigma^* \mid {prod}(x) = 2 \}. \] The number of states in a minimum state DFA for \( L \) is ___________. (Answer in integer)
- GATE CS - 2025
- Theory of Computation
- Regular expressions and finite automata
- Consider two grammars \( G_1 \) and \( G_2 \) with the production rules given below:
\[ G_1: \begin{aligned} S &\to \text{if } E \text{ then } S \,|\, \text{if } E \text{ then } S \text{ else } S \,|\, a \\ E &\to b \end{aligned} \] \[ G_2: \begin{aligned} S &\to \text{if } E \text{ then } S \,|\, M \\ M &\to \text{if } E \text{ then } M \text{ else } S \,|\, c \\ E &\to b \end{aligned} \] whereif,then,else,a,b,care the terminals.
Which of the following option(s) is/are CORRECT?- GATE CS - 2025
- Theory of Computation
- Regular expressions and finite automata
- Let \( G_1, G_2 \) be Context-Free Grammars (CFGs) and \( R \) be a regular expression. For a grammar \( G \), let \( L(G) \) denote the language generated by \( G \). Which ONE among the following questions is decidable?
- GATE CS - 2025
- Theory of Computation
- Regular expressions and finite automata
Match LIST-I with LIST-II \[\begin{array}{|c|c|c|}\hline \text{ } & \text{LIST-I} & \text{LIST-II} \\ \hline \text{A.} & \text{A Language L can be accepted by a Finite Automata, if and only if, the set of equivalence classes of $L$ is finite.} & \text{III. Myhill-Nerode Theorem} \\ \hline \text{B.} & \text{For every finite automaton M = $(Q, \Sigma, q_0, A, \delta)$, the language L(M) is regular.} & \text{II. Regular Expression Equivalence} \\ \hline \text{C.} & \text{Let, X and Y be two regular expressions over $\Sigma$. If X does not contain null, then the equation $R = Y + RX$ in R, has a unique solution (i.e. one and only one solution) given by $R = YX^*$.} & \text{I. Arden's Theorem} \\ \hline \text{D.} & \text{The regular expressions X and Y are equivalent if the corresponding finite automata are equivalent.} & \text{IV. Kleen's Theorem} \\ \hline \end{array}\]
\[\text{Matching List-I with List-II}\]
Choose the correct answer from the options given below:
- CUET (PG) - 2025
- Data Science
- Regular expressions and finite automata
Questions Asked in GATE CS exam
In a 4-bit ripple counter, if the period of the waveform at the last flip-flop is 64 microseconds, then the frequency of the ripple counter in kHz is ______________. {(Answer in integer)}
- GATE CS - 2025
- Flip-Flop
Consider the following C code segment:
int x = 126, y = 105; do { if (x > y) x = x - y; else y = y - x; } while (x != y); printf("%d", x);The output of the given C code segment is ____________. (Answer in integer)
- GATE CS - 2025
- Programming in C
The following two signed 2’s complement numbers (multiplicand \( M \) and multiplier \( Q \)) are being multiplied using Booth’s algorithm:
Multiplicand (\( M \)) Multiplier (\( Q \)) 1100 1101 1110 1101 1010 0100 1010 1010 The total number of addition and subtraction operations to be performed is __________. (Answer in integer)
- GATE CS - 2025
- Complementation
The maximum value of \(x\) such that the edge between the nodes B and C is included in every minimum spanning tree of the given graph is __________ (answer in integer).
- GATE CS - 2025
- Programming and Data Structures
Consider the following C program
The value printed by the given C program is __________ (Answer in integer).- GATE CS - 2025
- Programming in C