Automata Season - 1

Greetings,

Updating this blog after a very long time..

Let’s see something useful in terms of preparation of UGC-NET exam
Let me start with the most boring (of most people) – Automata. But it’s in fact the easiest and the most interesting one if we understand the simple logic.

Say, 1024 x 2 = 2048 is a big calculation if we memorize 2 - multiplication table. But if we know the logic of multiplying every digit by 2 and taking carry on to next integer, then this multiplication can be done in no time.

Hierarchy of Automata:

Type	Grammar	Language	Automata
Type 0	Unrestricted	Recursively enumerable Language	Turing Machines
Type 1	Context sensitive	Context Sensitive Language	Linear Bounded Automata
Type 2	Context Free	Context Free Language	Push Down Automata
Type 3	Regular	Regular Language	Finite Automata

Properties of Grammars are tabulated below:

No.	Property	Type 3	Type 2	Type 1	Type 0
1	Union  U	Closed	Closed	Closed	Closed
2	Intersection  П	Closed	Not closed	Closed	Closed
3	Inverse  I	Closed	Not closed	Not closed	Not closed
4	Difference L1 – L2	Closed	Not closed	Not closed	Not closed
5	Homomorphism	Closed	Closed
6	L*	Closed	Closed	Closed	Closed
7	LR	Closed	Closed
8	L1.L2	Closed	Closed	Closed	Closed
9	L-1		Closed

 Mathematical Model:

No	Name	Mathematical Notation	Transition functions
1	Finite Automata	{Q, S, F, Ʃ, ρ}	NFA: Q x Ʃ -> 2Q DFA: Q x Ʃ -> Q Moore: λ: Q -> Δ Meale: Q x Ʃ -> Δ
2	Push Down Automata	{Q, q0, Ʃ, δ, Γ, Z}	Q x Ʃ x Γ -> Q x Γ*
3	Linear Bounded Automata	{Q, Ʃ, δ, q0, ₵, $, F, Γ}
4	Turing Machine	{Q, q0, Ʃ, δ, Γ, B, F}	Q x Γ -> Q, Γ*, (L/R)

Symbol	Description	Symbol	Description
Q	Set of states	q0	initial state
S	Start state	Γ	set of stack (PDA) / tape(TM) symbols
F	Set of Final States F Ϲ Q	Z	starting element of stack
Ʃ	Set of input symbols	B	Blank
ρ, δ	Transitions	$	right end marker
₵	left end marker	L/R	Left or Right move

To be Continued..
Next post will be updated soon on short notes on these kinds of automata