CSE 350 Final Review

[T/F] A DFA that only recognizes the empty language must not have any final states.

• True

• False

[T/F] The language of all regular expressions is context free.

• True

• False

[T/F] All NFAs can be converted to have just 1 final state.

• True

• False

Converting an NFA with 4 states into an equivalent DFA requires no more than ___ states.

What is the minimum number of states in a DFA that recognizes the language

L = {w | #a's mod 3 = 0 AND #b's mod 4 = 0}?

• 4

• 7

• 12

• 16

[T/F] The set of context free languages is closed under set difference.

• True

• False

[T/F] L = {even length palindromes} can be recognized by a deterministic PDA.

• True

• False

[T/F] A PDA with a finite stack is equivalent to a DFA.

• True

• False

[T/F] The intersection between a context-free language and a regular language is always context-free.

• True

• False

[T/F] If A is a PDA that recognizes a language L, swapping the accepting and non-accepting states in A makes a PDA for the complement of L.

• True

• False