Automata Season - 2

Hi,

This is a continuation of the previous post on automata.

1. Basic Terms:

1. String – valid sequence of inputs / sequence of characters from £

2. Language – pattern of strings accepted by automata / set of all strings accepted by automata

3. £ - Transition – without reading any input, moves from one state to another state

4. Regular expression - Representation of language

5. / - either or (a/b = a or b)

6.  . –  one element followed by another (a.b = ab)

7. + - Positive closure (one or more occurrences)

8. * - Kleen Closure (zero or more occurrences)

9. Regular expression is used in Lexical analysis phase of compiler

10. Homomorphism – substitution of strings for symbols

2. Finite Automata:

 Finite Automata has no remembering capacity. It can be divided into:

(1) Deterministic Finite Automata – DFA   (2) Non Deterministic Finite Automata – NFA

NFA	DFA
Single input -> Multiple states	one input -> one state
Will not have transitions for all inputs in a state	Each state has transitions equal to number of inputs
£ transitions	No £ transitions
(Q, q0 , F, Ʃ , δ) where δ - { Q x Ʃ -> 2Q }	(Q, q0 , F, Ʃ , δ) where δ - { Q x Ʃ -> Q }

There are 2 outputs:

(1) Accepting a string – read entire string and reach one of the final state

(2) Rejecting a string – ends up with one of the non-final states

There are 2 kinds of FA:

(1) Acceptors – automaton that accepts / rejects a string

(2) Transducers – automata that gives output other than yes / no

Transducers: Finite Automata with outputs:

There are two kinds:

(1) Moore Machine

(2) Mealey machine

Moore Machine	Mealey Machine
Output is associated with states	Output is associated with transition
Mathematical:  ( Q, q0, F, Ʃ, δ, Δ, λ ) δ : Q x Ʃ -> Q      λ(qi) -> qj Ʃ - input   Δ -  output λ: Q -> Δ  (o/p function mapping)	Mathematical:  ( Q, q0, F, Ʃ, δ, Δ, λ ) δ : Q x Ʃ -> Q      λ(qi) -> qj Ʃ - input   Δ -  output λ: Q x £ -> Δ

3. Grammar:

G = {V, T, P, S}

V – Variables or non terminals (represented by capital letter)

T – Terminals / constants (lower case letters, terminals can’t be expanded)

P - Productions (A -> α | A derives α | α: combination of terminals and non terminals[sentential form])

S – Start symbol (S £ V)

Context free grammar – since single non terminal is used, it is called CFG

Context sensitive grammar – if it imposes any constraint (stating context rule)

Derivation – Process of deriving strings by taking appropriate productions using S as start symbol

(Derivable – valid mathematical expression, not derivable – invalid mathematical expression)

Ambiguous Grammar – if both leftmost and rightmost derivations are applicable

Mathematical expressions have – (1) Precedence (2) Associativity

Normal forms in Grammar:

(1) Chomsky Normal Form (2) Greibach Normal Form

FA	PDA
Regular expression	Context free Grammar
Read from input tape	Read from input tape and stack

NPDA	DPDA
λ transitions	λ transitions are allowed provided there’s no transition for any other element
All transitions are not specified
Multiple transitions for a single input symbol
Has facility to identify end of string even when there is no marker	End of string indication must be there

4. Turing Machines

It is a Mathematical model which represents any computing systems. It is classified as:

(1) Recognizers – Acceptors of Language

 (2) Transducers – computation of values (works only with integers)

It is capable of moving towards left and right. It is based on current state and tape symbol, transition happens. There is a need to specify the move left or right.

There are 2 functions:

(1) Totally recursive functions – All answer values are in integer

(2) Partially recursive functions – All answers won’t be an integer

5. Linear Bounded Automata:

It is a restricted form of TM. It is a non-deterministic Turing Machine satisfying 2 important conditions.

(1) Its input alphabet includes 2 special characters: ₵ as left end marker and $ as right end marker and ->  as standard end marker

(2) LBA has no moves to the left of the symbol or right of the symbol or can print another symbol over ₵, $

(3) Every CSL is recursive. 

6. Undecidable Problem:

(1) Recursively enumerable language (if Turing Machine exists to solve but does not halt on all inputs)

(2) Non Recursively enumerable language (that has no TM to solve)

7. Closure Properties:

(1) Closure Properties of regular sets:

Union, intersection, complement, difference, reverse, kleen closure, concatenation, homomorphism, inverse homomorphism – all are regular

(2) Closure Properties of recursive languages:

Union, Intersection and complement – all are recursive

To be Continued..

Next post will be a set of predictable questions guessed from the previous years question papers of UGC-NET.

Dont expect exactly the same even this year.. But typical models can be assumed..