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 GATE CS Theory of Computation Questions
- Consider the following context-free grammar \(G\), where \(S\), \(A\), and \(B\) are the variables (non-terminals), \(a\) and \(b\) are the terminal symbols, \(S\) is the start variable, and the rules of \(G\) are described as:
\[ S \to aaB \mid Abb \] \[ A \to a \mid AaA \] \[ B \to b \mid bB \] Which ONE of the languages \(L(G)\) is accepted by \(G\)? - A regular language \(L\) is accepted by a non-deterministic finite automaton (NFA) with \(n\) states. Which of the following statement(s) is/are FALSE?
- Consider the following two languages over the alphabet \( \{a, b\} \): \[ L_1 = \{ \alpha \beta \alpha \mid \alpha \in \{a, b\}^+ { and } \beta \in \{a, b\}^+ \} \] \[ L_2 = \{ \alpha \beta \alpha \mid \alpha \in \{a\}^+ { and } \beta \in \{a, b\}^+ \} \] Which ONE of the following statements is CORRECT?
- Consider the following two languages over the alphabet \( \{a, b, c\} \), where \( m \) and \( n \) are natural numbers. \[ L_1 = \{ a^m b^{m+n} c^{m+n} \mid m, n \geq 1 \} \] \[ L_2 = \{ a^m b^n c^{m+n} \mid m, n \geq 1 \} \] Which ONE of the following statements is CORRECT?
Consider the following deterministic finite automaton (DFA) defined over the alphabet, \( \Sigma = \{a, b\} \). Identify which of the following language(s) is/are accepted by the given DFA.
Top GATE CS Regular expressions and finite automata Questions
- 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?
- 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?
- 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? 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)
Top GATE CS Questions
- Which of the following sequences when stored in an array at locations A[1],..., A[10] forms a max-heap?
- The Lucas sequence Ln is defined by the recurrence relation: Ln = Ln−1 + Ln−2, for n ≥ 3, with L1 = 1 and L2 = 3. Which one of the options given is TRUE?
- Which of the following fields of IP header is/are always modified by any router before it forwards to IP Packet ?
- Which one of the following CIDR profix exactly represent the range of IP addresses 10.12.2.0 to 10.12.3.255?
- Consider an ethernet segment whose transmission is \(10^8\) bits per second. Maximum segment length \(500\ m\), speed of the provocation media velocity is \(2 × 10^8\) meter per second. What is the minimum frame size in bits ?