Sunday, December 26, 2010

Pushdown Automata

Pushdown Automata (PDA) is a computational model equivalent to Context Free Grammar (CFG).

A Pushdown Automata (PDA) is an Non-Deterministic Finite Automata (NFA) augmented with an infinitely large stack.

The additional memory enables recognition of some non-regular languages.


A Pushdown Automata (PDA) is essentially a Finite Automata with a Stack data structure as shown above.

A Pushdown Automata (PDA) can write an unbounded number of stack symbols on the stack and read these symbols later.

Writing a symbol onto the stack is called Pushing and it pushes all symbols on the stack one stack cell down.

Removing a symbol off the stack is called Poping and every symbol on the stack moves one stack cell up.

A Pushdown Automata (PDA) can access only the stack's topmost symbol in LIFO manner.

Now, We Consider how to describe precisely the abstract machine whose operations.we have sketched each move of the machine will be determined by three things.

(1) The Current State
(2) The Next Input
(3) The Symbol on top of the Stack

and will consist of two parts.

(1) Changing state ( Or staying in the same state)
(2) Replacing the top stack symbol by a string of zero or more symbols.

Friday, December 24, 2010

Context Sensitive Grammar CSG

Context Sensitive Grammars are more general than Context Free Grammar ( CFG ) and less so than Unrestricted Grammars.

The corresponding model of computation called Linear Bounded Automata ( LBA ).

Linear Bounded Automata lie between Pushdown Automata ( PDA )and Turing Machine ( TM ).


Significance of the phrase "Linear Bounded":-

In Linear Bounded Automata ( LBA ) tape head's motion is restricted to a portion of the tape bounded by
some Linear function of the input length.

Sunday, December 19, 2010

Algorithm to Minimize DFA

Algorithm To Minimize Deterministic Finite Automata (DFA)

Step - 1
Mark Final States and Non Final States as Distinguished.

Step - 2
Recursively iterating over all pairs of states.
For any transition of the form

δ(p,x) = r   δ(q,x) = s 

and for some x є Σ, if r and s are distinguishable, mark p and q as distinguish.

Step - 3
If on any iteration over all possible state pairs one fails to find a new pair of
states that are distinguishable, terminate.

Step - 4
All states that are not distinguishable are equivalent.

Saturday, December 18, 2010

Context Free Grammar

Context Free Grammar (CFG)


  • A Context Free Grammar is a "Machine" that creates a Language.
  • A Language created by a Context Free Grammar is called a Context Free Language (CFL).
  • The Class of Context Free Languages properly contains the class of Regular Language.



Applications of CFG.


  • CFG are extensively used to specify the syntax of programming Languages, and now the structure of document like XML's Document Type Definition
  • CFG used to develop Parser. (Specification and Compilation of Programming Language)
Meaning of Context Free?

If at some point in a derivation we have obtained a string α containing the variable A, then we may continue by substituting β  for A, No matter what the string α1  and α2 are. That is independent of the Context. 

Wednesday, December 8, 2010

Questions for GTU Remedial Exam


1.  Define Following. [1 – 2 Marks]
  1. Principle of Weak Induction
  2. Deterministic Finite Automata (DFA)
  3. Non- Deterministic Finite Automata (NFA)
  4. NFA – Λ
  5. Λ – Closure of a Set of States for NFA-Λ
  6. Context Free Grammar (CFG)
  7. Pushdown Automata (PDA)
  8. Turing Machine
  9. Linear Bounded Automata (LBA)
  10. Pumping Lemma for Regular Language
  11. Pumping Lemma for Context Free Language
2. Differentiate followings. [2 – 3 Marks]
  1. DFA Vs. NFA Vs. NFA – Λ
  2. Direct Proof Vs. Indirect Proof
  3. Σ* Vs. Σ+
  4. Accept by Empty Stack Vs. Accept by Final State
3. Answer the following. [6 – 7 Marks]
  1. Explain Chomsky Hierarchy in detail.
  2. Discuss Turing Machine and explain Configuration of TM.
  3. What do you mean by Ambiguity? Discuss Derivation Tree and Ambiguity in context of CFG.
  4. Prove that “Any language accepted by any Finite Automaton is regular”.
  5. Which machine is used to recognize CFL? Explain it with its data structure.
Explain the different way by which it accepts Language.
4. Prove that for every n>0



5. Suppose a and b are integers with 0 ≤ a ≤ b. Prove that for every n≥1,
    bn – an is divisible by b-a.
6. Draw DFA for following
  1. All string over {0, 1} that ends with substring 001.
  2. All string over {0, 1} that contains substring 0110.
  3. All string over {0, 1} that starts with substring 011.
  4. Given that L1 = {x є (0,1)* | x ends with 11}, L2 = {x є (0,1)* | x ends with 10}
Give FA for L1, L2 and L1 U L2
       e.    For Regular Expression (a + b)* abb.
7. Calculate the Following.  δ*(1,aabbab)       (ii)   δ*(1,bab) for following NFA.



8. A Transition table is given for an NFA- Λ with Seven States.
q
δ(q, a)
δ(q, b)
δ(q, Λ)
1
ø
ø
{ 2 }
2
{ 3 }
ø
{ 5 }
3
ø
{ 4 }
ø
4
{ 4 }
ø
{ 1 }
5
ø
{ 6, 7 }
ø
6
{ 5 }
ø
ø
7
ø
ø
{ 1 }
       Find:   (i)   Λ ({3,4})    (ii)    δ*(1, ab)
9. Using Algorithm Draw an NFA accepting the same Language.

 
10. Using Subset Construction Draw FA for Given.

11. The Length of a function can be defined as follow.
(i)  | Λ |=0
(ii) For any x є Σ* and any a є Σ,    |x a| = |x| + 1
     Prove that for every x and y in Σ*, |x y| = |x| + |y|
12. Convert      aa (ba)* + b*aba*    to an NFA-Λ.
13. For the following FA, Use the minimization algorithm to find a Minimum State FA     recognizing the same Language.

 
14. Prove that Following Languages are Not Regular.
  1. Pal the Language of Palindrome over {0, 1}
  2. L = { 0n  | n is Prime }
  3. L = { 0i 1j | i > j }
15. Find out CFG for L = { x є {0, 1}* | n0(x) = n1(x) }
16. Show that following grammar is Ambiguous and Find out Unambiguous grammar for same.
             S A | B.   A aAb | ab.   B abB | Λ
17. Convert following CFG in to CNF.
S AACD.
A aAb | Λ  
C aC | a
D aDa | bDb | Λ
18. Find out CFG for
  1. L = { ai bj ck  | j=i or j=k }
  2. L = { ai bj   | i < 2j  }
19. Construct DPDA for Language L = { x є {a, b}* | na (x) > nb (x) }
        Show the Sequence of Moves for Input String : bbabaa
20. Give Transition table and Transition Diagram for the Language of Palindrome.
       Draw Computation Tree for Input String aba.
21. Construct TM Accepting Language pal of Palindrome.
       Show the Sequence of Moves for Input String (1) ab (2) bab
23. Construct TM to compute n mod 2. Show the Sequence of Moves for (1) n=2  (2) n=3
24. Prove that L = { x є {a, b, c}* | na(x) < nb(x) and na(x) < nc(x) } is not Context Free
       Language.
25. The language L  {0,1}* is defined as follows:
1. 0 є L
2. For any x  є L, 0x є L
3. For any x and y in L, all the strings 1xy, x1y, and xy1 are in L
4. No other strings are in L.
Prove that every element of L has more 0’s than 1’s Using Structural Induction.