edited by
2,205 views
1 votes
1 votes

The pumping lemma says that every regular language has a pumping length $p,$ such that every string in the language can be pumped if it has length $p$ or more. If $p$ is a pumping length for language $A,$ so is any length $p^{'}\geq p.$ The minimum pumping length for $A$ is the smallest $p$ that is a pumping length for $A.$For example, if $A = 01^{*},$the minimum pumping length is $2.$ The reason is that the string $s=0$ is in $A$ and has length $1$ yet $s$ cannot be pumped$;$ but any string in $A$ of length $2$ or more contains a $1$ and hence can be pumped by dividing it so that $x = 0, y = 1,$ and $z$ is the rest. For each of the following languages, give the minimum pumping length and justify your answer$.$

  1. $0001^{*}$
  2. $0^{*}1^{*}$
  3. $001\cup 0^{*}1^{*}$
  4. $0^{*}1^{+}0^{+}1^{*}\cup 10^{*}1$
  5. $(01)^{*}$
  6. $\epsilon$
  7. $1^{*}01^{*}01^{*}$
  8. $10(11^{*}0)^{*}0$
  9. $1011$
  10. $\sum^{*}$
edited by

1 Answer

0 votes
0 votes

Pumping Lemma states, if $n$ is the length of any string of length $s,$ the sequence of state $q_{1},q_{3},q_{20},q_{9},........q_{13}$ has length $n+1.$ Because we know, $n$ is atleast $p$ (where $p$ is pumping length), and we know $n+1$ is grater than $p,$ the number of states in the language $M.$ The sequence must contain a repeated state, i.e. fancy name of Pegion-hole Principle 

 

If the string M divide in $xyz$, then $x$ goes from $r_{1}$ to $r_{j}$, $y$ takes $M$ from $r_{j}$ to $r_{j}$ and $z$ takes from $r_{j}$ to $r_{n+1}$ and we know that $xy^{i}z$ for $i\geq 0$ and $j\neq l$, so $y> 0$ and ${\color{Red} {l\leq p+1}}$, so $\left | xy \right |\leq p$

 

$a)$ Minimum pumping length $4.$ Because every string need to be divided in atleast $3$ parts $x,y,z.$ Otherwise it cannot be pumped.

$b)$ Minimum pumping length $1.$

$c)$ Minimum pumping length $4.$

$d)$ Minimum pumping length $3.$

$e)$ Minimum pumping length $2.$

$f)$Minimum pumping length $1.$

$g)$Minimum pumping length $3.$

$h)$Minimum pumping length $4.$

$i)$Minimum pumping length $5.$

$j)$Minimum pumping length $1.$

Ref:https://www.cs.auckland.ac.nz/~cristian/mfcsdir/cris/2010/tutorials/tut03_Solutions.pdf

edited by

Related questions

0 votes
0 votes
0 answers
3
admin asked Apr 30, 2019
282 views
Let $\sum=\{0,1,+,=\}$ and $ADD=\{x=y+z|x,y,z$ $\text{are binary integers,and}$ $x$ $\text{is the sum of}$ $y$ $\text{and}$ $z\}.$ Show that $\text{ADD}$ is not a regular...