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
- 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
- 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
- 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
Questions Asked in GATE CS exam
- With respect to a TCP connection between a client and a server, which of the following is true?
- GATE CS - 2026
- Computer Networks
- Let $P, Q, R, S$ be relational schemas. Let ``$\rightarrow$'' indicate a functional dependency (FD) in this context. Which of the following best describes the meaning of a functional dependency?
- GATE CS - 2026
- Database Management Systems
- Let a Non-deterministic Finite Automaton (NFA) have 6 states over a finite alphabet. Which of the following cannot be the number of states in a minimal Deterministic Finite Automaton (DFA) that is equivalent to this NFA?
- GATE CS - 2026
- Theory of Computations
- A certain processor uses a fully associative cache of size 16 kB. The cache block size is 16 bytes. Assume that the main memory is byte addressable and uses a 32-bit address. How many bits are required for the Tag and the Index fields respectively in the addresses generated by the processor?
- GATE CS - 2026
- Computer Organization and Architecture
- Consider $Z = X - Y$, where $X$, $Y$ and $Z$ are all in sign-magnitude form. $X$ and $Y$ are each represented in $n$ bits. To avoid overflow, the representation of $Z$ would require a minimum of:
- GATE CS - 2026
- Computer Organization and Architecture