Exams › GATE › Technical
Let \(L_1 = \{w \in \{0,1\}^* \mid w\text{ has at least as many occurrences of }110\text{ as }011\}\). Let \(L_2 = \{w \in \{0,1\}^* \mid w\text{ has at least as many occurrences of }000\text{ as }111\}\). Which one of the following is true?
- L1 is regular but not L2
- L2 is regular but not L1
- Both L1 and L2 are regular
- Neither L1 nor L2 are regular
Correct answer: Both L1 and L2 are regular
Solution
The difference between the counts of 110 and 011 depends only on local transitions in the string and can be captured by a finite-state machine. Similarly, the difference between counts of 000 and 111 can be determined by a finite automaton using bounded memory. Therefore both languages are regular.
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 →