Friday, April 13, 2012

Language Accepted by PDA

Language Accepted by PDA

There are two ways of accepting an input string PDA

a. Accept by Final state
After consuming the input, PDA enters a final state. The content of the stack is irrelevant.

b. Accept by empty stack
After consuming the input, stack of the PDA will be empty. The current state could be final or non-final state.

Both methods are equivalent. It is possible to covert a PDA accept by final state to another PDA accept by empty stack and also the vice versa. Usually the languages that a PDA accept by final state and PDA by empty stack are different. 

For example the language {L = a^nb^m | n >= m}, the appropriate PDA could be by final state. After consuming the input, the stack may not be empty.

Simplification of CFG

The goal is to take an arbitrary Context Free Grammar G = (V, T, P, S) and perform transformations on the grammar that preserve the language generated by the grammar but reach a specific format for the productions. A CFG can be simplified by eliminating

1. Useless symbols
Those variables or terminals that do not appear in any derivation of a terminal string starting from Start variable, S.

2. e - Productions
A   ®  e, where A is a variable

3. Unit production
A   ®  B, A and B are variables

Sunday, April 8, 2012

Pumping Lemma

What is Pumping Lemma?

The Pumping Lemma is the formal tool we use to prove that given Language is not Regular.

The Pumping Lemma sometimes just states that there exists some integer N, The Pumping Lemma is not true for all integers greater than the number of states in the machine.

Also note that the Pumping Lemma states
"For all x є L with |x| >=N, there exists Strings u,v and w"

The Pumping Lemma can not be used to prove that a given Language is Regular.

The Proof that a language is not regular is always by Contradiction.

All strings in the language can be "Pumped" if they are at least as long as certain values, called "Pumping Length"

Means Each such string in the language contains a section that can be repeat any number of times with resulting string remaining in the language.