Regular Languages & Finite Automata

One or more correct

• A32
• B65
• C1
• D128

One or more correct

• A$L_1$ is regular
• B$L_1 \cup L_2$ is regular
• C$\overline{L_2}$ is context-free
• D$L_1$ is context-free

One or more correct

• A$L(D_1) = L(D_2)$
• B$L(D_1)$ is a proper subset of $L(D_2)$
• C$L(D_1) \cap L(D_2) = \{\epsilon\}$
• D$(L(D_1) \cup L(D_2))^*$ consists of all strings in $\{0,1\}^*$ whose length is divisible by 3

One or more correct

• A$L$ may have an accepting NFA with $< n$ states.
• B$L$ may have an accepting DFA with $< n$ states.
• CThere exists a DFA with $\le 2^n$ states that accepts $L$.
• DEvery DFA that accepts $L$ has $> 2^n$ states.

Single correct

• ABoth $L_1$ and $L_2$ are regular languages.
• B$L_1$ is a regular language but $L_2$ is not a regular language.
• C$L_1$ is not a regular language but $L_2$ is a regular language.
• DNeither $L_1$ nor $L_2$ is a regular language.

One or more correct

• AThe set of all strings containing an even number of $b$'s.
• BThe set of all strings containing the pattern $bab$.
• CThe set of all strings ending with the pattern $bab$.
• DThe set of all strings not containing the pattern $aba$.

One or more correct

• A$\{a^m b^n \mid m, n \ge 0\}$
• B$\{a, b\}^* \cap \{a^m b^n c^{m-n} \mid m \ge n \ge 0\}$
• C$\{w \mid w \in \{a, b\}^*,\ \#_a(w) \equiv 2 \pmod 7, \text{ and } \#_b(w) \equiv 3 \pmod 9\}$
• D$\{w \mid w \in \{a, b\}^*,\ \#_a(w) \equiv 2 \pmod 7, \text{ and } \#_a(w) = \#_b(w)\}$

Numerical answer

One or more correct

• A$L_1 = L_2$ if and only if $L_1 \cap \overline{L_2} = \phi$
• B$L_1 \cup L_3$ is not regular
• C$\overline{L_3}$ is not regular
• D$\overline{L_1} \cup \overline{L_2}$ is regular

One or more correct

• AStates 2 and 4 are distinguishable in $M$
• BStates 3 and 4 are distinguishable in $M$
• CStates 2 and 5 are distinguishable in $M$
• DAny string $w$ with $n_0(w) = n_1(w)$ is in $L(M)$

Numerical answer

Single correct

• A$0^*1(0 + 10^*1)^*$
• B$0^*(10^*11)^*0^*$
• C$0^*1(010^*1)^*0^*$
• D$0(1 + 0^*10^*1)^*0^*$

Single correct

• A$(00)^* + 1(11)^*$
• B$0^* + (1 + 0(00)^*)(11)^*$
• C$(00)^* + (1 + (00)^*)(11)^*$
• D$0^+ + 1(11)^* + 0(11)^*$

Numerical answer

Single correct

• A$1(0^*11)^*$
• B$0(0 + 1)^*$
• C$1(0 + 11)^*$
• D$1(110^*)^*$

Answer key coming soon

letter → [A-Za-z]
digit  → [0-9]
id     → letter (letter | digit)*

Single correct

• AAutomaton (A) in the figure
• BAutomaton (B) in the figure
• CAutomaton (C) in the figure
• DAutomaton (D) in the figure

Answer key coming soon

Single correct

• AThe language generated by $G$ is $(a + b)^*$
• BThe language generated by $G$ is $a^*(a + b)b^*$
• CThe language generated by $G$ is $a^*b^*(a + b)$
• DThe language generated by $G$ is not a regular language

Answer key coming soon

Numerical answer

Answer key coming soon

Single correct

• A$ab^*bab^* + ba^*aba^*$
• B$(ab^*b)^*ab^* + (ba^*a)^*ba^*$
• C$(ab^*b + ba^*a)^*(a^* + b^*)$
• D$(ba^*a + ab^*b)^*(ab^* + ba^*)$

Answer key coming soon

One or more correct

• A$L_1$ and $L_2$ are regular.
• B$L_1$ and $L_2$ are context-free.
• C$L_1$ is regular and $L_2$ is context-free.
• D$L_1$ and $L_2$ are context-free but not regular.

Answer key coming soon