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