TOC 1 A

Let L be the set of all strings over {a, b} that do not contain "aaa" as a substring. What is the minimum number of states in a DFA accepting L?

• 2

• 3

• 4

• 5

Which of the following regular expressions defines the language of all strings over {a, b} that end with "ab"?

• (a+b)ab

• ab(a+b)

• (a+b)a(b)

• (a+b)*ba

Consider a DFA that accepts binary strings divisible by 3. How many states does the minimal DFA have?

• 2

• 3

• 4

• 5

A language L over alphabet {a, b} is defined by the regular expression (a+b)abb. Which of the following strings is in L?

• abab

• abb

• baab

• bba

Given an NFA with ε-transitions and 4 states, what is the maximum number of states in the equivalent DFA after removing ε-transitions and determinizing?

• 8

• 16

• 4

• 10

Consider a DFA with 6 states. What is the worst-case number of equivalence classes during DFA minimization?

• 6

• 5

• 2

• Depends on language

What language is recognized by the regular expression (a+b)a(a+b)(a+b)?

• Strings with 'a' as the 3rd-last symbol

• Strings starting with 'a'

• Strings ending in 'aa'

• Strings of length 3

Which of the following cannot be accepted by any DFA?

• Strings over {0,1} with even number of 0s

• Palindromes over {0,1}

• Strings ending with 01

• Strings that start and end with same symbol

Which regular expression denotes all strings over {0,1} that have even number of 1s?

• (0+11)*

• (00+11+01+10)*

• (0*(1010))

• None of the above

The DFA minimization algorithm merges two states if:

• They are final states

• They have identical transitions

• They are indistinguishable for all strings

• They are unreachable