Michael Sipser Edition 3 Exercise 1 Question 54 (Page No. 91)

Question

Consider the language $F=\{a^{i}b^{j}c^{k}|i,j,k\geq 0$ $\text{and if}$ $ i = 1$ $\text{then} $ $ j=k\}.$

1. Show that $F$ is not regular.
2. Show that $F$ acts like a regular language in the pumping lemma. In other words, give a pumping length $p$ and demonstrate that $F$ satisfies the three conditions of the pumping lemma for this value of $p.$
3. Explain why parts $(a)$ and $(b)$ do not contradict the pumping lemma.

Answer 1

a. case 1: when i=1 F=$ab^nc^n$. it is DCFG

    case 2: when i$\neq$1 F=$a^ib^jc^k$ | i,j,k$\geq$0

                 this is aaa*b*c* $\bigcup$ b*c*

   F=$ab^nc^n$ $\bigcup$ {aaa*b*c* $\bigcup$ b*c*}

    =DCFG $\bigcup$ regular

    =DCFG

_____________________________________________________________________

b. Three conditions of Pumping Lemma

    for any regular language L, there exists an integer p(pumping length) such that for all strings w$\varepsilon$L and |w|$\geq$p (i.e.
    the length of string is atleast p), there exists x, y, z such that w=xyz (the string can be broken down into three parts) and

    1. |xy|$\leq$p length of xy must not exceed the pumping length

    2. |y|$\geq$1 y cannot be null string

    3. for all integer i$\geq$0, $xy^iz\varepsilon L$

    taking p=4

    case 1: x=ε, y=bbbb, z=ε

                w=$(bbbb)^i$

                for i=0, w=ε

                for i=2, w=bbbbbbbb

                for all i, w belongs to L

                It behaves like regular language

  case 2: x=aa, y=bb, z=c

               w=$aa(bb)^ic$

               i=0, w=aac

               i=5, w=aabbbbbbbbbbc

               for all i, w belongs to L

 

Pumping Lemma test will fail when x=a, y=bbb, z=ccc

Comments

@Verma Ashish

why case 1 is incorrect?

when i$\neq$1 then there is no restriction. there could be any number of a's followed by any number of b's followed by any number of c's

---

No no ..

$DCFL\cup regular= DCFL$  always.

I was saying about part a, case2--

When $i\neq 1$ then you can't write F=a*b*c* , because it will also generate $ab^jc^k$ (j,k>=0), which is not satisfying the condition that if i=1 then j=k

---

oh got it!

thanks for pointing that out :)

will update the answer