Table Of Contents
  • Turing Machines
  • Chomsky Hierarchy
  • Context-Free Languages

Turing Machines

A Turing machine accepts languages that are produced by type 0 grammars. It is a mathematical model made up of an infinite length tape that is broken down into cells where the inputs are added. A Turing machine has a head where the input tape is read and a state register that stores the Turing machine’s state. The internal state of a Turing machine is often changed after the input symbol has been read.

Chomsky Hierarchy

Chomsky hierarchy is a concept in the theory of computation that divides grammars into four types:

Type 0

This type of grammar is also known as unrestricted grammar. They consist of all the formal grammars. A Turing machine identifies type 0 grammar language.

Type 1

Type 1 is a context-sensitive grammar. It creates languages that are identified by the linear bound automata.

Type 2

Type 2 is a context-free grammar that generates languages. These languages are identified by a pushdown automata

Type 3

Type 3 is the regular grammar. They are languages that are accepted by finite-state automation.

Context-Free Languages

These are languages produced by context-free grammars. A context-free language set is similar to pushdown automata recognized languages’ set. Also, all regular languages fall under context-free languages. All regular languages are classified as context-free languages. However, we cannot classify context languages as regular languages. Context-free languages are used to generate most arithmetic equations. Context-free languages and grammar are used in natural language processing and computer language design.