virtualgate's picture

PDA and CFL

Classification Of Grammer

Acc to chomsky grammer are classified into four type:

1) Type-3 Grammer:

                A--->αB/β

               A,B ∈ V

              α,β  ∈ T*

This is also called as right linear grammer(RLG).

 

              A--->Bα/β

               A,B ∈ V

              α,β  ∈ T*

This is also called as left linear grammer(LLG).

V=variable

T=terminals

 

NOTE:- Whatever language is generated by type-3 grammer they are nothing but regular grammer.

 

2) Type-2 Grammer:(Context Free Grammer)

            A--->α  ,A ∈ V

                  α ∈(V ∪ T)*

If a grammer is regular then it is definetly context free  but if a grammer is context free then it may not be regular.

 

e.g

anbmcn+m/n,m>=1

Sol:

S--->aSc/aAc

A--->bAc/bc

 

3)Type-1 Grammer:(Context sensitive grammer)

               x--->y

               where x,y ∈ (V ∪ T) 

                and |x|=<|y|

this mean always the grammer is non contracting.

e.g:-

S--->abc/aAbc

Ab--->bA

Ac--->Bbcc

bB--->Bb

aB--->aa/aaA

laguage generating by this CSG is?

Sol:

anbncn    n>=1

        

4) Type-0 Grammer:( unrestricted Grammer)

A grammer is called unrestricted if all the production are of the form u--->v where u is in (v ∪ T)+

v is in (v ∪ T)*

v is a varible and T is a terminal

Contributor's Info

Created:
0Comment
Introduction To PushDown Automata

In order to accept Context free language we need a machine which is similer to finit automata. It is nothing but a finit automata to which a memory is added i.e stack.

                   FA + Stack=PDA

(Q,∑,δ,q0,Z0,F,X)

Q : Finite Set of states

∑ : Input symbol

δ  : Transition Function

q0 : Initial Symbol

Z: Bottom of the stack

F  :  Set of final states

X  : Stack alphabet( means what are the symbol that we allow to be present on to the top of the statck)

 PDA is of two type:

1. Deteministic PDA:

 

δ  : Q x {∑ ∪ ∈} x X     ---->   Q x X*

 

 

2. Non Detesministic PDA:

 

δ  : Q x {∑ ∪ ∈} x X      ---->    2Q x X*

 

 

Contributor's Info

Created:
0Comment
PDA
Content covered: 

PDA

More Less
0Comment
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
Removal Technique

Some times in grammar we have some impurities, which we need to remove.
Types of impurities we have are as follows:
1. Elimination of Epsilon Production:  If ε  is present in the grammar, then we should have at least one ε production, but you can remove others.

   Steps with example:

     1.   S --> aSb/aAb

           A--> ε

  • find out all the ε production: Here, A--> ε is ε production.
  • find out all the nullable variables: here nullable variable is A
  • Write down all the production with and without nullable variables , and remove ε 

         S --> aSb/ aAb/ ab

  • If any variable is not present then remove it from all the production.

     S --> aSb/ ab

 

    2.   S-->  ABAC

           A-->  aA/ ε

          B-->   bB/ε

          C-->  c

Solution:

        S--> ABAC / BAC / ABC / BC/ AC/ C/ AAC

        A-->  aA / a

       B-->  bB / b

       C-->   c

   

   3.   S -->  AbaC

           A-->   BC

           B-->  b/  ε

           C-->  D/ ε

           D-->  d

Solution: 

       S--> AbaC/ baC / Aba/ ba

       A--> C /BC / B / ε

       B--> b

       C--> D

       D--> d

 But some time removing ε production can give us unit production, which we   also need to remove. for example in above production C--> D is a unit production.

 

2. Elimination of unit production: 

When you see a unit production, just replace the corresponding variables with its terminal that are present in its production.

examples:

      1. S -->  Aa /B

           B-->  A / bb

           A-->  a / bc / B

        Solution:

         S --> Aa/ a/ bb/ bc

         B--> a / bc / bb

         A--> a / bc / bb

 Sometime eliminating unit prodction gives you useless symbol or useless     prodction , for example here in the solution B--> a / bc / bb , this is uselss   prdcution beacsue B is not reachable from start symbol S so we need to   remove  it.

 

3. Eliminating useless production:

          Steps:  1. first check whether the variable is reachable from the start symbol.

                         2. Check if the production contains a useful symbol.

                         3. Useful Symbols are : Start variable, terminals, and variable which have productions made up of only these two things.

Examples: 

     1.  S--> AB / a

           A--> BC / b

          B--> aB/   C

          C--> aC / B 

   Solution : 

        Useful symbol are {a,b, S,A}

        now if you see B and C does not have production which are made of useful            symbol so remove them and remove all the production that contains B and            C

              S--> a

              A-->b

      now you see that A is not reachable from S so remove it also

              S--> a

 

   2.  S--> ABC / BaB

         A--> aA / BaC / aaa

         B--> bBb / a

         C--> CA / AC

   Solution: 

          Useful Symbol are: {a,b,A,B,S} but C is useless so remove it and remove all              the  production that conatins C

          S--> BaB

          A--> aA/ aaa

          B--> bBb / a

     but A is not reachable fro S so remove it and all its prodction

          S--> BaB

          B--> bBb / a

   

     

 

Contributor's Info

Created:
0Comment
Linear Bounded Automata(LBA)

We can't increase the power of turing machine by giving them more tape and facility. If we limit the tap to be used as stack and non determiniam then it will ac t as a push down automata, Now come to linear bounded automata ,LBA is a TM which restricted ,means it is not suppose to use beyond the input.
LBA= TM +Tape(input)
Note: 1)This LBA is less powerful than TM. '
eg. anbncn
not accepted by PDA, but this language can be accepted by LBA accordingly. So LBA is powerful than PDA
2)Whenever we talking about power ,we are talking about taking them as non deterministic machine in all the cases.[i.e FA,PDA,LBA,TM ]

 

These are example which are accepted by LBA.

1) L ={anbncn  ,n>=1}

 

2) L={an!  ,n>=0}

 

3) L={a ,n=m2  ,m>=1}

 

4)L={an  ,n is a prime}

 

5) L={an  ,n is not a prime}

 

6) L={ww   ,w∈ {a,b}+ }

 

7) L={wn   ,w∈ {a,b}+ ,n>=1}

 

8)L={wwwr  ,w∈ {a,b}+}

Contributor's Info

Created:
0Comment

  • This quiz contains 10 questions on the topic Context Free Language
  • Lean well before you attempt the quiz
  • You can attempt the quiz unlimited number of times.

Difficulty Level:  intermediate

  • This quiz contains 5 questions on the topic PDA/CSL
  • Lean well before you attempt the quiz
  • You can attempt the quiz unlimited number of times.

Difficulty Level:  intermediate