How to proof using only pumping lemma that something is not regular?

54 Views Asked by At

In formal languages I need to proof using the pumping lemma that the following is not regular:

$A_1=\{1^m0^n10^n|n,m\in \mathbb{N}\}$

How to achieve that? Any help is upvotet

1

There are 1 best solutions below

0
On BEST ANSWER

$\mathcal L=\{1^m0^n10^n| m,n \in \mathbb{N}\}$ regular language?

Hint:

No, we will prove with the pumping lemma, let us choose the word $z=0^p10^p$

Spoiler:

$\quad|z|>p$ So $z=uvw,\quad |uv|\leq p, \quad |v| \geq 1, \quad uv^iw\in \mathcal L \quad i\geq0$ For all $i\neq 1$ the word not in $\mathcal L$ because $u,v$ will be in the first zero's part or in the last zero's part or will be here: $00..\overbrace{..0100}^{u,v}000$