Showing posts from 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

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.

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.

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 DefinitionCFG 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.

Questions for GTU Remedial Exam