Saturday, December 8, 2012

Kleene's Theorem : Applications

Kleene's Theorem :

Part - I :

"Any Regular Language can be Accepted by a Finite Automaton"


The Construction in the proof of above theorem provide an algorithm for constructing an NFA-^ corresponding to a given Regular Expression.

If we have NFA-^, M1 and M2, the proof of above theorem provide us with algorithms for constructing new NFA-^ to recognize the Union, Concatenation, and Kleene * of the Corresponding Languages.


"The Language Accepted by any Finite Automaton is Regular"


The Construction in the proof of above theorem provides way to find a Regular Expression Corresponding to a given Finite Automaton.

Friday, October 19, 2012

Find out regular expression for given NFA - ^

Find out regular expression for given NFA - ^.


Find RegExp for Given NFA - 1


Find RegExp for Given NFA - 2


Find RegExp for Given NFA - 3


(1) a (ab + baa )*  (aba)*  (aa + bab) a

(2) (ab*a + baaba)*

(3) ( (a*b + ab*) ab)+

Tuesday, June 26, 2012

Types of Turing Machines

(1) What is Multi-Head Turing Machine?

A k-head TM has some k heads. The heads are numbered 1 through k, and move of the TM depends on the state and on the symbol scanned by each head. In one move, the heads may each move independently left or right or remain stationary.

(2) What is a 2-way infinite tape TM ?

In 2-way infinite tape TM, the tape is infinite in both directions. The leftmost square is not distinguished. Any computation that can be done by 2-way infinite tape can also be done by standard TM. 

(3) What is a Multi-tape Turing machine?

A multi-tape Turing machine consists of a finite control with k-tape heads and k tapes ; each tape is infinite in both directions. On a single move depending on the state of finite control and symbol scanned by each of tape heads ,the machine can change state print a new symbol on each cells scanned by tape head, move each of its tape head independently one cell to the left or right or remain stationary.

(4) What is a Multidimensional TM?
The device has a finite control , but the tape consists of a k-dimensional array of cells infinite in all 2k directions, for some fixed k. Depending on the state and symbol scanned , the device changes state , prints a new symbol and moves its tape head in one of the 2k directions, either positively or negatively ,along one of the k-axes.


Ogdens lemma

Ogden's lemma

Let L be a Context Free Language. Then there is a constant n such that if z is any word in L, and we mark any n or more positions of z  “distinguished” then we can write z = uvwxy such that:

(1) v and x together have atleast one distinguished position.

(2) vwx has at most n distinguished positions and

(3) for all i>=0  uviwxiy is in L.

Applications of Context Free Languages

Applications of Context Free Languages
  • Defining programming languages.
  • Formalizing the notion of parsing.
  • Translation of programming languages.
  • String processing applications.

Uses of Context Free Grammars
  • Construction of compilers.
  • Simplified the definition of programming languages.
  • Describes the arithmetic expressions with arbitrary nesting of balanced parenthesis { (, ) }.
  • Describes block structure in programming languages.
  • Model neural nets.

Monday, June 25, 2012

Chomsky Hierarchy

Chomsky Hierarchy


Types of Languages


Types of Grammars

Type Language or Grammar Accepting Device
3 Regular Finite Automata
2 Context Free Pushdown Automata
1 Context Sensitive Linear Bounded Automata
0 Recursively Enumerable Turing Machine

Friday, April 27, 2012


  • The Context Free Grammar is an Essential Concept for the implementation of compiler and other programming Language Processor.
  • Tools such as YACC take a CFG as input and produce a Parser, the component of a compiler that deduce the structure of the program being compiled.
  • Suppose that G  is a Context Free Grammar over an Alphabet Σ. To Parse a string  x є Σ* is often useful.
  • Parsing a statement in a programming Language, for example, is necessary in order to classify it according to syntax.
  • Parsing an algebraic expression is essentially what allows us to evaluate the expression.
  • There are main two different way of parsing.
        (1) Top Down Parsing
        (2) Bottom Up Parsing

Thursday, April 19, 2012

Turing Machine Overview

Turing Machine

An Abstract machine introduced by the English Mathematician Alan Turing and for that reason now called Turing Machine

The work of Turing and his contemporaries provided much of the theoretical foundation for the modern computer.

A Turing Machine (TM) will have a finite alphabet of symbols and a finite set of states.

TM has a linear "Tape", which has a left end and is potentially infinite to the right.

The Tape is marked off into squares, each of which can hold one symbol from the alphabet, If a square has no symbol on it, we say that it contains Blank Symbol.

We may think of squares as being numbered, Left to Right , Starting with 0. It is not necessary to refer to the numbers in describing the operation of machine.

The reading and writing being done by a tape head, which any time centered on one square of the tape.

A single move is determined by the current state and the current tape symbol, and consists of three parts.

(1) Replacing the symbol in the current square by another, possibly different symbol.

(2) Moving the tape head one square to the right or left or leaving it where it is.

(3) Moving from the current state to another, possibly different state.

The Tape serves as the input device the memory available for use during computation and the output device.

In Turing Machine processing a string is no longer restricted to a single left-to-right pass through the input.

The tape head can move in both direction and erase or modify any symbol it encounters.

The machine can examine part of the input, modify it, take time out to execute some computations in a different area of the tape, Return to reexamine the input, repeat any of these actions, and perhaps stop the processing before it has looked at all the input.

TM contains two states Ha that indicates acceptance and Hr that indicates rejection.

If the machine is intended simply to accept or reject the input string, then it can move to the appropriate halt state once it has enough information to make a decision.

If it is supposed to carry out some other computations, the accepting state indicates that the computation has terminated normally,

The state Hr can be used to indicates that the system is “Crashed”, arising from some abnormal situation in which the machine cannot carry out its mission as expected.

In any case, the computations stop if the Turing Machine reaches either of the Two Halt State.

It is also possible for the computation not to stop, and for the Turing Machine to continue making moves forever.

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.