Formal grammars and languages respecting to Automata theory

• Formal grammars
• Classification of grammars and formal languages. Chomski's hierarchy
• Turing Theory

Formal grammars

A grammar G is a set of 4 elements. It was defined by a mathematician-linguist Naom Chomski as follows.

Definition:

A formal grammar G is a set of 4 elements

G: {N,T,S,P},

• Nis a set of non-terminal symbols, or variables,
• T is a set of terminal symbols, or constatets,
• S is a set of special symbols
• P is a finite set of rules.

Terminal and non-terminal symbols create a vocabulary V=N T. The set S includes start state S₀ and also finite states F. The rules P can be phrase structural rules or substitution rules and also transform rules.

Classification of grammars and formal languages. Chomski's hierarchy

Formal languages includes 4 classes correspondingly to 4 types of grammars (Table 3.1):

• 1 - natural languages, with a system of arbitrary rules (for example, English languages),
• 2 - context languages, with rules depending on context (programming languages LISP, PROLOG),
• 3 - context-free languages, in which the rules are started with non-terminal symbols (for instatece, PASCAL, C)
• 4 - regular languages, mostly restricted (for example, assembler)

Such hierarchy is known as hierarchy of N. Chomsky.

Table 1: Classification of Formal Languages (Chomsky Hierarchy)

Type of language	Grammar	Example
0 - natural	G: {V=NT,S,P} P: x->y, x,yV	P.: x->y, S -> x, xAy -> w, x,y,wV, AN
1 - context	G: {V=NT,S,P} P: xAy -> xwy, a,b,wV, AN	G: T={a,b,c,d}, N={I,A,B}, P.:I -> aAI, bI -> ba, AI -> ABA, A -> b, AI -> A, bBA -> bcdA
2 - context free	G: {V=NT,S,P} P: A -> x, xV, AN	G: T={a,b }, N={I }, P.: I -> aI, I -> bIb, I -> aa, I -> bb
3 - regular	G: {V=NT,S,P} P: A -> x, A -> aB (right-side) lub A -> Ba (left-side), aT, A,BN	G: T={a,b }, N={I,A}, P.: I -> aI, I -> aA, A -> bA, A -> S

Turing Theory

Automata theory is a part of mathematical linguistics, which describes formal languages through Automaton. The most popular model of Automaton is Turing machine. In Turing theory each type of language corresponds to an Automaton model (Table 3.2).

Table 2: Classification of Formal Languages and Automata

Definition:

Turing machine is an abstract Automaton, or model of a device for computations, which includes:

• a infinite (tape),
• read / write head) ,
• a (computer), which is in a state belonging to a finite set of internal states.

The program of Automaton behaviour is a finite state of rules described as below:

If the computer is in state Q_i and symbol t_i is read on the tape, move the read/write head k steps to the right (left if k is negative) and write symbol s_j on the tape; then switch the machine to state Q_j.

Definition:

Abstarct Automata A is a set of 4 elements

A: {T,Q,R,F,S},

T - is an input alphabet,

Q - is a set of internal states of the Automaton, or non-terminal symbols,

R - is a finite state of transition rules,

F - is a set of finite states,

S - is a set of output or stack symbols.

The relations between formal grammars and Automaton are shown in Table:

Table 3: Relation between Formal grammar and Automaton