What is the minimum number of states in a DFA accepting the language $L = {w$ in {a, b}* | w contains 'aba' as a substring}?
For substring 'aba': states represent prefixes matched: $\epsilon (q0), 'a' (q1), 'ab' (q2)$, and 'aba' (q3, dead accept state). Total 4 states.
Which of the following regular expressions represents all binary strings ending with '101'?
Any binary string ending in '101' has any prefix of 0s and 1s, represented by (0+1)*, followed by the suffix 101.
Let L1 be a regular language and L2 be a context-free language. Which of the following is ALWAYS regular?
For a regular language L1 and any language L2, the right quotient L1/L2 = {x | exists y in L2 such that xy in L1} is regular. The construction can mark DFA states of L1 from which some string in L2 can reach a final state.
What is the result of Arden's Theorem for the equation $R = Q + RP$ where P does not contain $\epsilon$?
Arden's Theorem states that if P does not contain $\epsilon$, the equation $R = Q + RP has a unique solution R = QP*$.
Minimum number of states in a DFA accepting binary numbers divisible by 5 is:
DFA tracking remainders mod 5 requires 5 states (remainders 0, 1, 2, 3, 4).