product construction and DFAs

a

If $L_{1}$ is regular and $|L_{1}| = k$ and $L_{2}$ is non-regular, then $L_{1} \cap L_{2}$ is regular

$\boxed{\text{True}}$

$L_{1} \cap L_{2} = L_{3}$ implies $L_{3} \subseteq L_{1}$ (intersection)

Given that $|L_{1}| = k$, meaning there is a fixed number of string in $L_{1}$ ,therefore $L_{1}$ is finite. Given that all finite language are regular, $L_{1} \cap L_{2}$ will contain at-most $k$-string, making $L_{3}$ regular

b

If $L_{1}$ is regular and $L_{2}$ is non-regular, then $L_{1} \cup L_{2}$ is regular

$\boxed{\text{False}}$

If $L_{1} = \{ ab \}$ where it only accepts the string $ab$, and $L_{2} = \{ a^n b^n | n \geq 0 \}$, then $L_{1} \cup L_{2} = \{ a^n b^n | n \geq 0 \}$, which is non-regular

c

$\forall L_{1}$ such that $L_{1}$ is a non-regular language, $\exists L_{2}$ such that $L_{2}$ is regular and $L_{1} \subseteq L_{2}$

$\boxed{\text{True}}$

For all non-regular languages $L_{1}$, they can be seen as a subset of $\Sigma^{*}$. Given that $\Sigma^{*}$ is regular (a DFA with one accepting state), this means the aforementioned statement holds.

a

$M$ accepts all strings which begin with $b$ but do not contain the substring $bab$

b

$\mathcal{L}(M) = \{ a^i b^j c^k | i + j + k \text{ is a multiple of 3} \}, \Sigma = \{ a,b,c \}$

c

$\mathcal{L}(M) = \{ x | \text{ There are at least two a's in the last three characters of } x \}$

Via production construction, create a DFA $M$ such that

$$\mathcal{L}(M) = \{ a^n b^m | \text{n or m is a multiple of 3} \}$$

$M_{1}$:

$M_{2}$:

table 1: product construction of $\mathcal{L}(M) = \{ a^n b^m | \text{n or m is a multiple of 3} \}$

note: the state that are not used will be crossed out

Question

NFA which accepts all string in which the third last character is an a. Then via subset construction create an equivalent DFA

$\boxed{\text{NFA}}$

table 2: subset construction for given NFA

$\boxed{\text{DFA}}$

Question

Create a sound argument that the concatenation of two regular languages is also regular. Specifically, if $L_{1}$ and $L_{2}$ are regular then $L_{1} L_{2}$ is also regular. This does not need to be a formal proof, but the argument should be very convincing.

Hint: if $L_{1}$ and $L_{2}$ are regular you can make “machines” for them; how would you make a “machine” for $L_{1} L_{2}$.

Given $L_{1}$ and $L_{2}$ are both regular languages, there exists and DFA $M_{1}$ and $M_{2}$ that recgonize $L_{1}$ and $L_{2}$ respectively

Let $M_{1} = (Q_{1}, \Sigma, \delta_1, q_{01}, F_{1})$ and $M_{2} = (Q_{2}, \Sigma, \delta_2, q_{02}, F_{2})$

We can try to construct a NFA $N$ to recognize $L_{1} L_{2}$, where we combine both states of $M_{1}$ and $M_{2}$ via product construction, then we add $\epsilon$-transition from every accepting state in $F_{1}$ to start state $q_{02}$ of $M_{2}$

Conceptually, for a string $w \in L_{1} L_{2}$, split $w = uv, u \in L_{1}, v \in L_{2}$

• If $N$ process $u$ in $M_{1}$, reach accept states $F_{1}$, then $\epsilon$ transition to $q_{02}$, then process $v$ in $M_{2}$, ending in $F_{2}$
• if no valid splits, then it rejects the string
• for empty string: if $\epsilon \in L_{1}$ then it can transition to $M_{2}$, and vice versa.

Given that regular language are also closed under NFAs, if we can build a NFA which proves that $L_{1} L_{2}$ is regular

$\boxed{\text{q.e.d}}$