Introduction To Automata Theory

 

1.    Introduction

 

1.1.   Symbol:  a, b, c, d, ……, z, A, B, C, ………. Z, 0, 1, 2,3, …….9  etc.

1.2.   Alphabet: An alphabet is a set of finite non-empty set of symbol. It is   denoted by ∑ (sigma).

Ex:       ∑   = {a, b} is alphabet with symbol a and b.

             ∑   = {0, 1} is binary alphabet.

             ∑   = { 0, 1, 2, ….., 9}  is decimal alphabet.

1.3.  Language over alphabet:  Language is a set of words / strings over an alphabet.  It denoted by L.

Ex:       if  ∑  = { a } then L=  {a, aa, aaa, …..}                              

 if  ∑   = {a, b} then L   = {aa, ab, ba, ………}                     L

1.4.  String over alphabet: A string is any sequence of zero or more symbols over the given alphabet ∑ . String is the member of any language.

·         Empty string (ɛ  or ^ )

·        Empty string is also called as “NULL string”.

Ex :       Let L₁ be a language over ∑  = {a}

             L1 ={a ,aa, aaa, ………}

             String = a, aa, etc .

       1.5 Operations on strings

a.      Length of a string: The number of symbols in the sequence of given string is called “length of a string”

a.      Length of string ab=  |ab|=2, where ∑={a, b}

b.      |ɛ| = 0, the length of empty string is zero.

c.      |a|=1, |abb|=3

 

b.       Substring of a string:  A sequence of symbols from any part of the given string over an alphabet is called “Substring of a string”.

 Ex :         Let ∑ = {a, b}

                        Then L₁ = {ɛ, a, b, aa, bb, aba, bab, ….}

                          Possible strings= ɛ, a, b, aba etc.

                          Zero length substring:  ɛ

                          One length substring:  a, b

                          Two length substring: aa , bb , ab , ba

c.      Power of an alphabet :

                   Let    ∑ = {a ,b}

·        ∑⁰ = {ɛ }:  set of zero length string.

·        ∑¹ = {a, b}: set of one length string.

·        ∑² = {ab, ba}: set of two length strings.

·        ∑³ = {aaa, aab, aba, abb, baa, bba, bbb}: set of three length strings.

1.6 Operators

v Kleene Star Closure(*) : ∑* is the set of all strings over symbol ∑. It is unary operator.

                ∑* = ∑⁰  U ∑¹  U ∑²  U ∑³      U ……

Ex:            Let ∑ = {a, b}

                 Than ∑*   =  ∑⁰  U ∑¹  U ∑²  U ….

                                      = {ɛ} U {a} U {ab, ba} U …….

                                          = { ɛ, a, ab, ba, ……….}

v  Positive Closure (∑⁺) : ∑⁺ is the set of strings over ∑ except an empty string.

                  ∑+ = ∑¹ U ∑² U ∑³ U ……

Ex:      Let ∑ = {a, b}

                 Than ∑⁺   = ∑¹  U ∑²  U  ∑³….

                                      ={a} U {ab, ba} U {aaa, bbb, aba, bab bba, aab} U…….

                                                = {a, ab, ba, aaa, bbb, aba, bab, bba, aab ……….}

v Concatenation Operator(.): It combines two or more alphabets / strings to make one string.

Let L1 ={a, b}

String s1=a

String s2=b

String s1s2=ab

Exercise:

1.      Generate language L1 of length two over ∑ (a,b).

2.      Generate language L1 over  ∑ (a,b), in which string starts with a.

3.      Generate language L1 over  ∑ (a,b), in which string starts with a and ends with b.

4.      Generate language L1 over  ∑ (a,b), in which string starts with a and ends with b and string should be minimum two length.

5.      Generate language L1 over  ∑ (a,b), in which string starts with two consecutive a.

6.      Generate language L1 over  ∑ (a,b), in which string ends with two consecutive b.