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
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
- The minimum number of states in a DFA accepting \( L = \{ w | w \text{ ends with } 01 \} \) over \( \Sigma = \{0, 1\} \) is _______ .
- AP PGECET - 2025
- Theory of Computation
- Regular expressions and finite automata
- Which of the following is FALSE?
- AP PGECET - 2025
- Theory of Computation
- Regular expressions and finite automata
- Let \( P \) be a regular language and \( Q \) be a context free language such that \( Q \) is a subset of \( P \). Then which of the following is ALWAYS regular?
- AP PGECET - 2025
- Theory of Computation
- Regular expressions and finite automata
- The minimum number of nodes in a DFA that recognizes strings over \( \{a, b\} \) with length mod 3 = 0 are _______ .
- AP PGECET - 2025
- Theory of Computation
- Regular expressions and finite automata
Questions Asked in GATE CS exam
In the diagram, the lines QR and ST are parallel to each other. The shortest distance between these two lines is half the shortest distance between the point P and the line QR. What is the ratio of the area of the triangle PST to the area of the trapezium SQRT?
Note: The figure shown is representative
- GATE CS - 2025
- Geometry
Consider the following process information for Shortest Remaining Time First (SRTF) scheduling:
\[ \begin{array}{|c|c|c|} \hline \textbf{Process} & \textbf{Arrival Time (AT)} & \textbf{Burst Time (BT)} \\ \hline P1 & 0 & 10 \\ P2 & 1 & 13 \\ P3 & 2 & 6 \\ P4 & 8 & 9 \\ \hline \end{array} \]Find the turnaround time for each process.
- GATE CS - 2025
- Programming in C
- If IMAGE and FIELD are coded as FHBNJ and EMFJG respectively then, which one among the given options is the most appropriate code for BEACH?
- GATE CS - 2025
- GATE IN - 2025
- GATE MT - 2025
- GATE NM - 2025
- GATE TF - 2025
- Logical and Analytical Reasoning Skills
A square paper, shown in figure (I), is folded along the dotted lines as shown in figures (II) and (III). Then a few cuts are made as shown in figure (IV). Which one of the following patterns will be obtained when the paper is unfolded?
- GATE CS - 2025
- Paper Folding and Cutting
Consider the relationships among P, Q, R, S, and T:
• P is the brother of Q.
• S is the daughter of Q.
• T is the sister of S.
• R is the mother of Q.
The following statements are made based on the relationships given above.
(1) R is the grandmother of S.
(2) P is the uncle of S and T.
(3) R has only one son.
(4) Q has only one daughter.
Which one of the following options is correct?- GATE CS - 2025
- Blood Relations