Basics of Automata Theory

LEARNING OUTCOMES-

STUDENT(S) WILL ABLE TO EXPLAIN-

LO-1: Symbols, Alphabets & String and Kleene Star (*/+).

LO-2: Language & Regular Expression.

LO-3: Transition Function, State   Diagram & Transition Matrix.

LO-4: Grammar and conversion from   State Diagram to Grammar.

vAutomata is an ABSTRACT M/C.

vDEALS WITH THE LOGIC OF COMPUTATION WITH RESPECT TO SIMPLE M/C.

vAUTOMATA ENABLES COMPUTER SCIENTISTS AND ENGINEERS TO UNDERSTAND HOW  M/C COMPUTE THE FUNCTION AND SOLVE PROBLEMS.

SYMBOLS : a, b,------, z, .....    0, 1,------

ALPHABETS: (Ʃ)   <SET OF SYMBOLS>

i) Ʃ = {a, b}     ii) Ʃ = {a, b, 0, 1}

STRING: {ϵ, a, b, ab}, ϵ : Epsilon

 “LENGTH OF STRINGS”: | ^| = 0, |a| = 1, |ab| = 2

         

                                  Ʃ = { a, b}

                      Ʃ* ={^, a, b, ab, ba, aa, bb, aab, aabb,------}

KLEENE CLOSURE / KLEENE STAR

a* : {^, a, aa, aaa, aaaa,-------}

a+ : a* - ^ = {a, aa, aaa,-----}

Power of ‘Ʃ’:

Ʃ = {0, 1}

Ʃ 0 = {^},  Ʃ1 = {0, 1},  Ʃ2 = {00, 11, 01, 10}, Ʃ3 = {000, 001, 010, 011, 100, 110, 111}

 

Universal Set :

Ʃ* = Ʃ0 U  Ʃ1 U Ʃ2 U Ʃ3 U Ʃ4 U-------

    = {^} U {0,1} U {00, 01, 10, 11} U--------

LANGUAGE: SUBSET OF Ʃ*
    -SET OF STRINGS CHOOSEN FROM Ʃ*

EX:

Ʃ ={0, 1} “ALPHABETS OF BINARY DIGIT”

L1 = {SET OF ALL STRING OF LENGTH 2}

  = {00, 01, 10, 11}                  : FINITE LANGUAGE

L2 = {SET OF ALL STRINGS STARTS WITH ‘1’}

  ={1, 10, 11, 100, 110, 111, 1000, 1001,-----}

                                 :INFINITE LANGUAGE

CLASS WORK: Ʃ ={0, 1}

L3 = {SET OF ALL STRINGS WHICH ENDS WITH ‘0’}

ASSIGNMENT: Ʃ ={0, 1}

L4 = {SET OF ALL STRING WHICH ENDS WITH ‘00’}

L5 = {SET OF ALL STRING WHICH HAS EQUAL NO OF   0’S AND 1’S}

L6 = {SET OF ALL STRING WHICH HAS EVEN NO OF   0’S}

L7 = {SET OF ALL STRINGS WHICH HAS EVEN NO OF   0’S AND EVEN NO OF 1’S}

Regular Expression: (R.E.)

Ʃ = {a, b}

a*     => {^, a, aa, aaa,-----}

 (ab)*    => {^, ab, abab, ababab,----}

(a+b)* => {^, a, b, aa, bb, ab, ba, aaa, aba,------}

(a+b)(a+b)--------(a+b)----(a+b)--------

a(b)*b   =>  {ab, abb, abbb, abbbb,-----}

b+ a*  =>   {b, bb, bbb,------, ba, baa, bba,---- }

ASSIGNMENT:

Ʃ = {a, b}

a(a+b)*  =>

(a+b)+ b   =>

ab(ab)*    =>

(a+b)*ab(a(ab)+)*   =>

(b(a+b)* + a(a+b)*)*   =>