Finite Automata: Regular Languages GATE 2016 Question #1571 with Solution

GATE 2016 · CS1 - Forenoon

Theory of ComputationFinite Automata: Regular LanguagesmediumMCQ1 mark

Which one of the following regular expressions represents the set of all binary strings having two consecutive 0s and two consecutive 1s?

A(0+1)* 0011 (0+1)* + (0+1)* 1100 (0+1)*B(0+1)* (00 (0+1)* 11 + 11 (0+1)* 00) (0+1)*C(0+1)* 00 (0+1)* + (0+1)* 11 (0+1)*D00 (0+1)* 11 + 11 (0+1)* 00

Related Theory of Computation PYQs

Which of the following languages is generated by the given grammar: S -> aS | bS | ε?

Which of the following decision problems are undecidable? I. Given NFAs N1 and N2, is L(N1) ∩ L(N2) = Φ? II. Given a CFG G and a s…

Consider the following grammars. \[ \begin{aligned} G_1 &: S \to aS \mid B, \quad B \to b \mid bB \\ G_2 &: S \to aA \mid bB…

Consider the transition diagram of a PDA with Σ = {a, b} and stack alphabet Γ = {X, Z}. Z is the initial stack symbol. Transitions…

Let X be recursive, Y be RE but not recursive. Let W and Z be languages such that Y' reduces to W, and Z reduces to X'. Which stat…

The number of states in the minimum sized DFA that accepts the language defined by the regular expression (0+1)* (0+1) (0+1)* is _…

Saved progressKeep answers, mock results and completion history across devices.

Adaptive practiceGet questions matched to your recent accuracy and difficulty level.

Bookmarks and notesBuild a personal revision list and record why a question was difficult.

Performance insightsSee weak subjects, accuracy trends, streaks and exam readiness.