Regex, pumping lemma

Give regular expression for the languages bellow

1.a

$$L = \{ a^nb^m \mid (n+m) \% 2 = 0 \}$$

1.b

$$L = \{ w \mid w \text{ does not contain the substring: } aba \}$$

1.c

$$L = \{ w \mid w \text{ has an even number of } b' \text{s}\}$$

Minimize the number of states in this DFA via quotient construction. Show all your steps, specifically in your table where you are “marking” nodes indicate which iteration you marked them on.

Final states $\{ 0, 3 \}$, and non-final states are $\{ 1, 2, 4, 5, 6, 7, 8, 9 \}$

Initial table with all pairs:

      0 1 2 3 4 5 6 7 8 9
    ---------------------
0   |   *       * *
1   | *   *       *
2   |   *   *       *
3   |     *   *       *
4   |       *   *     *
5   | *       *   *   * *
6   | * *       *   *   *
7   |     *       *   * *
8   |       * * *   *   *
9   |           * * * *

Mark based on final/non-final states:

      0 1 2 3 4 5 6 7 8 9
    ---------------------
0   |   ✓       ✓ ✓
1   | ✓
2   |       ✓
3   |     ✓   ✓       ✓
4   |       ✓
5   | ✓
6   | ✓
7   |
8   |       ✓
9   |

      0 1 2 3 4 5 6 7 8 9
    ---------------------
0   |   ✓       ✓ ✓
1   | ✓
2   |       ✓
3   |     ✓   ✓       ✓
4   |       ✓
5   | ✓
6   | ✓
7   |
8   |       ✓
9   |

      0 1 2 3 4 5 6 7 8 9
    ---------------------
0   |   ✓       ✓ ✓
1   | ✓
2   |   x   ✓
3   |     ✓   ✓       ✓
4   |       ✓
5   | ✓
6   | ✓
7   |
8   |       ✓
9   |

Using the Pumping Lemma, prove the following languages are not regular. Make your steps in the “game” and variable choices very clear for each question.

Pumping Lemma

There exists a pumping length $p$ such that $\forall s \in L, |s| \geq p$, we can write $s = xyz$ such that

i. $|y| > 0$

ii. $|xy| \leq p$

iii. $\forall i \geq 0, xy^iz \in L$

4.a

$$L = \{ a^{nm}b^ma^n \mid n,m \geq 0 \}$$

Assume $L$ is regular.

Let $s = a^{p^2}b^pa^p$. $s \in L$ since choosing $n=p,m=p$, and $|s|=p^2+2p \geq p$ for $p \geq 1$.

By the pumping lemma, we can write $s=xyz$ satisfying conditions i) and iii). Since $|xy| \leq p$, $y$ must consist of only $a$‘s. Let $y = a^k$ for $1 \leq k \leq p$.

Consider string $xy^0z = xz = a^{p^2-k}b^pa^p$. From condition iii), this must be in $L$.

However, $xz$ has the first block of $a$ to length $p^2-k$ and last block of length $p$. To be in $L$, we must have $p^2-k=p \cdot m$ for some integer $m$. But $p^2-k>p$ for $p \geq 2$, so there is no such $m$ exists, which means $xz \notin L$.

Thus, it contradicts the pumping lemma, and $L$ is not regular. $\square$

4.b

$$L = \{ww \mid w \in \Sigma^*\}$$

Assume $L$ is regular.

Let $s = a^pb^pa^pb^p$. $s \in L$ since chos\sin g $w=a^pb^p$ and $|s|=4p \geq p$ for $p \geq 1$.

By pumping lemma, we can write $s=xyz$ satisfying conditions i) and iii). Since $|xy| \leq p$, $y$ must consist of only $a$‘s. Let $y = a^k$ for $1 \leq k \leq p$.

Consider the string $xy^2z = xa^kya^kb^pa^pb^p$. By condition iii) of the pumping lemma, this must be in $L$.

However, $xy^2z$ to be in $L$, it must be the for of $ww$ for some $w \in \Sigma^*$. But the first half of $xy^2z$ is $a^{p+k}b^p$ and the second half is $a^pb^p$. Since $k \leq p$. So $xy^2z \notin L$.

Thus, it contradicts the pumping lemma, and $L$ is not regular. $\square$

4.c

$$L = \{ a^{k^3} \mid k \leq 0 \}$$

Assume $L$ is regular.

Let $s = a^{p^3}$. $s \in L$ since choosing $k=p$, and $|s|=p^3 \geq p$ for $p \geq 1$.

By the pumping lemma, we can write $s=xyz$ satisfying conditions i) and iii). Since $|xy| \leq p$, $y$ must consist of only $a$‘s. Let $y = a^k$ for $1 \leq k \leq p$.

Consider the string $xy^2z = xa^kya^kz = a^{p^3+k}$. By condition iii) of the pumping lemma, this must be in $L$.

However, $xy^2z$ to be in $L$, it must be of the form $a^{k^3}$ for some $k \leq 0$. $p^3 < p^3+k < (p+1)^3$, which means $p^3+k$ is not a perfect cube, so $xy^2z \notin L$.

Thus, it contradicts the pumping lemma, and $L$ is not regular. $\square$