Regex, pumping lemma

Problème 1.

Give regular expression for the languages bellow

1.a

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

$$L=(aa{)}^{\ast }(bb{)}^{\ast }+a(aa{)}^{\ast }b(bb{)}^{\ast }$$

1.b

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

$$L=b^{\ast }+b^{\ast }{a}^{+}{b}^{\ast }+b^{\ast }(a{b}^{+}{)}^{\ast }a{b}^{\ast }$$

1.c

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

$$L=a^{\ast }+a^{\ast }b{a}^{\ast }b{a}^{\ast }$$

Problème 2.

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   |

first iteration.

{0,2} -(a)→ {1,3}: not marked {0,2} -(b)→ {6,7}: not marked {0,3} -(a)→ {1,4}: not marked {0,3} -(b)→ {6,8}: not marked {0,4} -(a)→ {1,5}: not marked {0,4} -(b)→ {6,8}: not marked {0,7} -(a)→ {1,9}: not marked {0,7} -(b)→ {6,8}: not marked {0,8} -(a)→ {1,9}: not marked {0,8} -(b)→ {6,5}: not marked {0,9} -(a)→ {1,7}: not marked {0,9} -(b)→ {6,6}: not marked

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

second iteration.

{1,2} -(a)→ {2,3}: marked so we mark {1,2} {1,5} -(a)→ {2,0}:

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

sorry I gave up

Problème 3.

Your friend is looking at the formal definition of the pumping lemma and they think something is wrong

$$L\text{ is regular }⟹(\exists k\mid k>0:(\forall x,y,z\mid xyz\in L\wedge |y|>k:(\exists u,v,w\mid y=uvw\wedge v\ne ϵ:(\forall i|i\ge 0:xu{v}^{i}wz\in L))))$$

They understand the argument it is crafted around, that is, due to the fact that strings are arbitrarily long and a DFA has finite states there must be a segment of accepted strings which “loop” in the machine. However, they claim for the pumping lemma above to hold, $L$ must be infinite, because if $L$ was finite the argument about “looping” no longer holds. Therefore, the pumping lemma only holds when $L$ is infinite.

You can see where your friend is coming from, but they are incorrect. Why? Be precise in your argument, that is, show how if $L$ is finite, then

$$(\exists k\mid k>0:(\forall x,y,z\mid xyz\in L\wedge |y|>k:(\exists u,v,w\mid y=uvw\wedge v\ne ϵ:(\forall i|i\ge 0:xu{v}^{i}wz\in L))))$$

evaluates to true. (hint: If $L$ is finite, there is a “longest string”)

Solution

Let $\ell$ be the length of the longest string in $L$. We can choose a pumping length $k$ such that $k\ge \ell =\ell +1$.

Now let’s evaluate the following statement

$$(\forall x,y,z\mid xyz\in L\wedge |y|>k:(\exists u,v,w\mid y=uvw\wedge v\ne ϵ:(\forall i|i\ge 0:xu{v}^{i}wz\in L)))$$

Since $k>\ell$, there doesn’t exist a string $xyz\in L$ such that $|y|>k$. Therefore, antecendent of the implication $xyz\in L\wedge |y|>p$ is always false.

Therefore, the entire inner implication is vacuously true, and the entire statement is true. Therefore, the pumping lemma holds for finite languages.

Problème 4.

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|\ge p$, we can write $s=xyz$ such that

i. $|y|>0$

ii. $|xy|\le p$

iii. $\forall i\ge 0,x{y}^{i}z\in L$

4.a

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

Assume $L$ is regular.

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

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

Consider string $x{y}^{0}z=xz=a^{p^2-k}{b}^p{a}^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\ge 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 }^{\ast }\}$$

Assume $L$ is regular.

Let $s=a^p{b}^p{a}^p{b}^p$. $s\in L$ since chos\sin g $w=a^p{b}^p$ and $|s|=4p\ge p$ for $p\ge 1$.

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

Consider the string $x{y}^{2}z=x{a}^{k}y{a}^k{b}^p{a}^p{b}^p$. By condition iii) of the pumping lemma, this must be in $L$.

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

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

4.c

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

Assume $L$ is regular.

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

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

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

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

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