GATE Theory of Computation Flashcards
6 cards from real GATE practice questions. Tap to flip, then mark Knew It or Still Learning — missed cards come back until you master them.
Read the first 6 GATE Theory of Computation flashcards as text
Which of the following regular expressions matches all binary strings that contain at least one '1'?
Answer: (0+1)*1(0+1)*
The expression (0+1)*1(0+1)* matches any binary string that has at least one '1' anywhere in it.
The class of languages accepted by linear bounded automata (LBA) corresponds to:
Answer: Context-sensitive languages
Linear bounded automata, which are Turing machines with tape bounded by a linear function of input length, accept exactly the context-sensitive languages.
According to Rice's theorem, which of the following is decidable?
Answer: Whether a Turing machine has exactly 5 states
Rice's theorem applies to non-trivial semantic properties of a TM's language; the number of states is a syntactic property of the TM itself, which is decidable.
The pumping lemma for regular languages states that for any sufficiently long string w in a regular language, w can be split into xyz such that:
Answer: |xy| ≤ p and |y| > 0 and xy^i z ∈ L for all i ≥ 0
The pumping lemma requires |xy| ≤ p, |y| ≥ 1, and that pumping y any number of times (including zero) keeps the string in the language.
Which of the following problems about context-free grammars is UNDECIDABLE?
Answer: Is L(G₁) = L(G₂) for two CFGs G₁ and G₂?
The equivalence problem for context-free grammars — whether two CFGs generate the same language — is undecidable.
An epsilon-NFA (ε-NFA) differs from a standard NFA in that:
Answer: It allows transitions without consuming any input symbol
An ε-NFA allows ε-transitions — state transitions that occur without reading any input character — which simplify grammar-to-automata conversions.