Exams › GATE › Technical
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?
- Both \(L_1\) and \(L_2\) are regular languages.
- \(L_1\) is a regular language but \(L_2\) is not a regular language.
- \(L_1\) is not a regular language but \(L_2\) is a regular language.
- Neither \(L_1\) nor \(L_2\) is a regular language.
Correct answer: Neither \(L_1\) nor \(L_2\) is a regular language.
Solution
For \(L_1\), taking \(\alpha=\epsilon\) gives all nonempty strings, but taking nonempty \(\alpha\) forces a mirrored structure that is not regular. For \(L_2\), strings of the form \(a^n b a^n\) are included, and this classic language is not regular. Hence neither language is 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 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?
- 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.
⚔️ Practice GATE Technical free + battle 1v1 →