PDA Examples

1. an+mbnc   n,m>=1

it is  not regular language but DCFL as well as CFL

 

2. ambn+mcn  n,m>=1

it is  not regular language but DCFL as well as CFL

 

3. ambncn+m  n,m>=1

it is  not regular language but DCFL as well as CFL

 

4. ambmcndn  n,m>=1

it is  not regular language but DCFL as well as CFL

 

5. ambncmdn  n,m>=1

it is  not regular language  as well as  not CFL because  by the time you reaches c's  there will b'son the top of the stacks ,you can't match a's

            there fore if a language is not CFL then that willl not beDCFL or regular.

 

6.  ambncndm  n,m>=1

it is  not regular language but DCFL as well as CFL

  

7. ambicmdk  i,j,m>=1

it is  not regular language but DCFL as well as CFL

 

8.  8.  ambn   / m>n

it is  not regular language but DCFL as well as CFL

here push a's and when we see b's pop a's and then at least there should be one a should remain and go to final state.

8.  anb2n   / n>=1

here for every "a" push two a's and when see any b's pop a's.

  it is  not regular language but DCFL as well as CFL

9. anbn^2  / n>=1

it is  not regular language 

i can't put bn^2  in loop and i can't popup for one loop ,one a's

                therefore it is not possible to give any PDA either deterministic or Non deterministic.

∴ not CFL

 

10. wwr  /w∈(a,b)*

not regular not DCFL but CFL(NDCFL)

 

11. anbncm  /n>m

 

not regular

for such language PDA is not possible because when you pop all a's using b's then at that time only c's will be remain and there will nothing to compair  with c's i.e(m).

 

12. anbncndn  /n<=1010

 

since language  is bounded (i.e finit ) and every  finite language is regular therefore DCFL that means CFL.

 

13. XcY  / X,Y(0,1)*

it is nothing but set of all string containing c as a sub string

so it is regular 

therefore DCFL that means CFL.

 

14. aibjckdl      /i=k or j=l

CFL as well as DCFL

 

15. w /w∈{a.b} ,na(w)=nb(w)+1

 

DCFL as well as CFL

Contributor's Info

Created:
0Comment