Exams › GATE › Technical
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.
- The set of all strings containing an even number of b’s.
- The set of all strings containing the pattern bab.
- The set of all strings ending with the pattern bab.
- The set of all strings not containing the pattern aba.
Correct answer: The set of all strings ending with the pattern bab.
Solution
The DFA is structured to accept exactly those strings whose last three symbols are \(bab\). Such automata keep track of the longest relevant suffix seen so far. Therefore the accepted language is the set of strings ending with \(bab\).
Related GATE Technical questions
- Consider the following context-free grammar where the set of terminals is {a, b, c, d, f}: S → daT | Rf T → aS | baT | ε R → caTR | ε Which of the following is correct?
- For a Turing machine $M$, $\langle M\rangle$ denotes an encoding of $M$. Consider the following two languages: $L_1=\{\langle M\rangle \mid M$ takes more than 2021 steps on all inputs$\}$ $L_2=\{\langle M\rangle \mid M$ takes more than 2021 steps on some input$\}$
- Consider the 5-state DFA $M$ accepting the language $L(M)=(0+1)^*$. For any string $w\in(0+1)^*$, let $n_0(w)$ be the number of 0s in $w$ and $n_1(w)$ be the number of 1s in $w$. Which of the following statements is/are FALSE?
- A regular language $L$ is accepted by a nondeterministic 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\}^* \text{ and } \beta\in\{a,b\}^+\} \] \[ L_2=\{\alpha\beta\alpha \mid \alpha\in\{a\}^* \text{ and } \beta\in\{a,b\}^+\} \] Which ONE of the following statements is CORRECT?
- Consider the following languages over the alphabet \(\{a,b,c\}\), where \(m\) and \(n\) are natural numbers: \[ L_1=\{a^m b^m c^{m+n} \mid m,n\ge 1\} \] \[ L_2=\{a^m b^n c^{m+n} \mid m,n\ge 1\} \] Which ONE of the following statements is CORRECT?
⚔️ Practice GATE Technical free + battle 1v1 →