Exams › GATE › Technical

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?

1. The language generated by the grammar is finite.
2. The language generated by the grammar contains the string daabaf.
3. The language generated by the grammar contains the string cad aaf.
4. The language generated by the grammar contains the string cacadaaf.

Correct answer: The language generated by the grammar contains the string daabaf.

Solution

Starting from S → daT, choose T → aS and then S → Rf with R → ε, or more directly use T → baT and then ε to build the required pattern. The string daabaf can be generated by appropriate substitutions, so the language contains it.

Related GATE Technical questions

• 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?
• 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 →