For the shown DFA A, which are false? 1: Its language complement is context-free. 2: L(A)=L((11*0+0)(0+1)*0*1*). 3: A is minimal. 4: A accepts all binary strings of length at least two.
The DFA accepts strings containing at least one zero. Its two nonaccepting states have identical future behaviour and can merge, so 3 is false. Strings such as 11 are rejected despite length two, so 4 is false. A regular complement is context-free, and the given expression denotes a zero after an optional run of ones followed by any suffix. Thus 1,2 are true and D is correct.
More Regular Expressions and Finite Automata questions
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…
GATE 2010 CS (CS1) Q49– Which regular expression denotes all binary strings with an even number of ones?
GATE 2010 CS (CS1) Q51– Let w be any binary string of length n, and L the set of all its substrings. What is the…
