GATE 2012 CS (CS1) – Question 22

Theory of Computation · Regular Expressions and Finite Automata · 1 mark · Multiple choice

Over alphabet {a}, with ε the empty string, find the complement of the language accepted by the shown NFA.

Diagram for GATE 2012 CS (CS1) question 22

$\varnothing$
$\{\epsilon\}$
$a^*$
$\{a,\epsilon\}$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (B) $\{\epsilon\}$

Explanation

The first a reaches the accepting state. The two ε transitions return to the start, so any positive number of a’s is accepted, but the empty word is not. The complement relative to {a}* is precisely {ε}, B.

More Regular Expressions and Finite Automata questions

GATE 2012 CS (CS1) Q35 – L=ab,aa,baa. Which strings belong to L*? 1: abaabaaabaa; 2: aaaabaaaa; 3: baaaaabaaaab; 4:…
GATE 2012 CS (CS1) Q56 – Over 0,1, every three-symbol substring must contain at most two zeros; all words shorter…
GATE 2013 CS (CS1) Q18 – L₁=∅ and L₂=a. Evaluate L 1L 2* L 1*.
GATE 2013 CS (CS1) Q43 – For the shown DFA A, which are false? 1: Its language complement is context-free. 2:…
GATE 2011 CS (CS1) Q52 – Over alphabet a, L=\ank:k>0\, with fixed positive integer n. Find the smallest DFA state…
GATE 2011 CS (CS1) Q55 – DFA D has transitions p:a→s,b→q; q:a→t,b→r; r loops on a,b; s,t are accepting and each…

All Regular Expressions and Finite Automata questions →