Identify the language generated by the following grammar, where S is the start variable: S -> X Y X -> aX | a Y -> aYb | ε
The minimum possible number of states of a deterministic finite automaton that accepts the regular language L = { w1 a w2 | w1, w2…
Let δ denote the transition function and δ^ denote the extended transition function of the ε-NFA whose transition table is: q0: ε …
Consider the following languages: L1 = { a^p | p is a prime number } L2 = { a^n b^m c^(2m) | n >= 0, m >= 0 } L3 = { a^n b^n c^(2n…
Let L(R) be regular, L(G) be context-free, and L(M) be Turing acceptable. Which of the following decision problems are undecidable…
Consider the following grammar where S is the start symbol, and a and b are terminal symbols. S → aSbS | bS | ε Which of the follo…
Free account benefits
Public PYQs and reference pages stay free. Sign in when you want GATEverse to remember what you studied and guide what to practise next.