Automata Theory Notes

Theory of Automata

Text and Reference Material

  • John E. Hopcroft. Jeffery D. Ullman. Introduction to Automata Theory, Languages, and Computation. 1979. Addison-Wesley.
  • T.A. Sudkamp: Languages and Machines (Addison-Wesley, 2nd Edition, 1997)
  • Harry R. Lewis, Christos H. Papadimitriou: Elements of the Theory of Computation, Second Edition, 1998.
  • Daniel I. A. Cohen. Introduction to Computer Theory. Second Edition. 1997. John Wiley and Sons.
  • Michael Sipser. Introduction to the Theory of Computation. 1997. PWS Publishing Company.
  • Virtual university handouts CS402

Automata Theory

  • Automata Theory is a theoretical branch of computer science that deals with designing abstract self-propelled computing devices that follow a predetermined sequence of operations automatically.

What does Automata mean?

  • The term "Automata" is derived from the Greek word "αὐτόµατα" which means "self-acting".
  • An automaton (Automata in plural) is an abstract self-propelled computing device which follows a predetermined sequence of operations automatically.
  • It is the plural of automaton, and it means “something that works automatically”

Why Study Automata Theory

  • Finite automata are a useful model for many important kinds of software and hardware:
    1. Software for designing and checking the behavior of digital circuits
    2. The lexical analyzer of a typical compiler, that is, the compiler component that breaks the input text into logical units
    3. Automata theory is important because it allows scientists to understand how machines solve problems. An automaton is any machine that uses a specific, repeatable process to convert information into different forms. Modern computers are a common example of an automaton.
    4. If scientists didn't study automata theory, they would have a much more difficult time designing systems that could perform repeatable actions based on specific inputs and outputs. Scientists are able to design systems that can perform specific tasks, such as personal computer systems, automatic aircraft pilots and many more, by using automata theory.

Applications of Automata Theory

  • Automata theory plays major role in:
    • For designing of Lexical Analyzer of Compiler.
    • For recognizing the patterns using Regular Expression.
    • For the designing of Combination and Sequential circuits using Mealy and Moore Machines.
    • For the implementation of Spell Checker
    • For designing the Parsing phase of compiler(Syntax Analysis)
    • For implementation Stack applications
    • For Evaluating Arithmetic Expressions
    • For constructing syntactic parse trees for semantic Analysis
    • For implementation of Neural Network
    • For implementation of Robotics Applications
    • For implementation of Artificial intelligence

Introduction to languages

  • There are two types of languages
    • Formal Languages (Syntactic languages)
    • Informal Languages (Semantic languages)

Formal Languages

  • Formal Languages are used as a basis for defining computer languages
  • A predefined set of symbols and string
  • Formal language theory studies purely syntactical aspects of a language (e.g., word abcd)
  • Informal Languages such as English has many different versions.

Alphabets

  • Definition: A finite non-empty set of symbols (letters), is called an alphabet. It is denoted by Σ ( Greek letter sigma).
  • Example:
    • Σ=a,bΣ={a,b}
    • Σ=0,1Σ={0,1} //important as this is the language //which the computer understands.
    • Σ=i,j,kΣ={i,j,k}

NOTE:

  • A certain version of language ALGOL has 113 letters.
  • ΣΣ sigma (alphabet) includes letters, digits and a variety of operators including sequential operators such as GOTO and IF

Strings

  • Definition: Concatenation of finite symbols from the alphabet is called a string.
  • Example: If Σ=a,bΣ= {a,b} then a, abab, aaabb, ababababababababab

NOTE: EMPTY STRING or NULL STRING

  • Sometimes a string with no symbol at all is used, denoted by (Small Greek letter Lambda) λλ or (Capital Greek letter Lambda) ΛΛ, is called an empty string or null string.
  • The capital lambda will mostly be used to denote the empty string, in further discussion.

Words

  • Definition: Words are strings belonging to some language.
  • Example: If Σ=xΣ= {x} then a language L can be defined as
    • L=xn:n=1,2,3,…L={x^n : n=1,2,3,…} or L=x,xx,xxx,…L={x,xx,xxx,…}
  • Here x,xx,… are the words of L but not xy.

NOTE:

  • All words are strings, but not all strings are words.

Defining Alphabets- Guidline

  • 3 important rules for defining alphabets for language
    • Should not contain empty symbol (ΛΛ)
    • Should be finite
    • Should not ambiguous

Valid/In-valid alphabets

  • While defining an alphabet, an alphabet may contain letters consisting of group of symbols for example Σ1=B,aB,bab,dΣ1= {B, aB, bab, d}.
  • Now consider an alphabet Σ2=B,Ba,bab,dΣ2= {B, Ba, bab, d} and a string BababB.
Valid alphabet:
  • If there is suffix but not prefix then it is a valid Alphabet, While defining an alphabet of letters consisting of more than one symbols, no letter should be started with the letter of the same alphabet.
  • Valid Alphabet : Σ=a,ba,cΣ = {a, ba, c}
In Valid alphabet:
  • If there is prefix present in an alphabet then it is an invalid Alphabet. Invalid Alphabet : Σ=a,ab,cΣ = {a, ab, c}

  • This string (BababB) can be tokenized in two different ways

    • (Ba), (bab), (B)
    • (B), (abab), (B)
  • Which shows that the second group cannot be identified as a string, defined over Σ=a,bΣ = {a, b}.

  • As when this string is scanned by the compiler (Lexical Analyzer), first symbol B is identified as a letter belonging to ΣΣ, while for the second letter the lexical analyzer would not be able to identify, so while defining an alphabet it should be kept in mind that ambiguity should not be created.

Remarks:

  • While defining an alphabet of letters consisting of more than one symbols, no letter should be started with the letter of the same alphabet i.e. one letter should not be the prefix of another. However, a letter may be ended in the letter of same alphabet i.e. one letter may be the suffix of another.

Conclusion

  • Σ1=B,aB,bab,dΣ1= {B, aB, bab, d}
  • Σ2=B,Ba,bab,dΣ2= {B, Ba, bab, d}
  • Σ1Σ1 is a valid alphabet while Σ2Σ2 is an in-valid alphabet.

Length of Strings

  • Definition: The length of string s, denoted by |s|, is the number of letters in the string.
  • Example: Σ=a,bΣ={a,b} s=ababa |s|=5
Example:
  • Σ=B,aB,bab,dΣ= {B, aB, bab, d}
  • s=BaBbabd
  • Tokenizing=(B), (aB), (bab), (d)
  • |s|=4

Length of strings over n alphabets

  • Formula : numbers of strings of length ‘m’ define over alphabet of ‘n’ letters is nmn^m
  • Example: the language of strings of length 2, define over Σ=a,bΣ= {a,b} is L=aa,ab,ba,bbL={aa, ab, ba, bb} i.e number of string=222^2
  • the language of strings of length 3, define over Σ=a,bΣ= {a,b} is L=aaa,aab,aba,baa,abb,bab,bba,bbbL={aaa, aab, aba, baa, abb,bab, bba, bbb} i.e. number of string=232^3

Reverse of a String

  • Definition: The reverse of a string s denoted by Rev(s) or srs^r, is obtained by writing the letters of s in reverse order.
  • Example: If s=abc is a string defined over Σ=a,b,cΣ={a,b,c} then Rev(s) or srs^r = cba
Example:
  • Σ=B,aB,bab,dΣ= {B, aB, bab, d}
  • s=BaBbabBd
  • Rev(s)=dBbabaBB

Lecture 2 Defining Languages

  • The languages can be defined in different ways , such as Descriptive definition, Recursive definition, using Regular Expressions(RE) and using Finite Automaton(FA) etc.
Descriptive definition of language:
  • It is one of language defining methods

  • The language is defined, describing the conditions imposed on its words.

  • Example: The language L of strings of odd length, defined over Σ=aΣ={a}, can be written as L=a,aaa,aaaaa,…L={a, aaa, aaaaa,…}

  • Example: The language L of strings that does not start with a, defined over Σ=a,b,cΣ={a,b,c}, can be written as L={b, c, ba, bb, bc, ca, cb, cc, …}

  • Example: The language L of strings of length 2, defined over Σ=0,1,2Σ={0,1,2}, can be written as L={00, 01, 02,10, 11,12,20,21,22}

  • Example: The language L of strings ending in 0, defined over Σ=0,1Σ ={0,1}, can be written as L={0,00,10,000,010,100,110,…}

  • Example: The language EQUAL, of strings with number of a’s equal to number of b’s, defined over Σ=a,bΣ={a,b}, can be written as {Λ ,ab,aabb,abab,baba,abba,…}

  • Example: The language EVEN-EVEN, of strings with even number of a’s and even number of b’s, defined over Σ=a,bΣ={a,b}, can be written as {Λ, aa, bb, aaaa,aabb,abab, abba, baab, baba, bbaa, bbbb,…}

  • Example: The language INTEGER, of strings defined over Σ=−,0,1,2,3,4,5,6,7,8,9Σ={-,0,1,2,3,4,5,6,7,8,9}, can be written as

    • INTEGER = {…,-2,-1,0,1,2,…}
  • Example: The language EVEN, of stings defined over Σ=−,0,1,2,3,4,5,6,7,8,9Σ={-,0,1,2,3,4,5,6,7,8,9}, can be written as

    • EVEN = { …,-4,-2,0,2,4,…}
  • Example: The language anbn{a^n b^n}, of strings defined over Σ=a,bΣ={a,b}, as

    • anbn:n=1,2,3,…{a^n b^n : n=1,2,3,…}, can be written as {ab, aabb, aaabbb,aaaabbbb,…}
  • Example: The language anbnan{a^n b^n a^n}, of strings defined over Σ=a,bΣ={a,b}, as

    • anbnan:n=1,2,3,…{a^n b^n a^n: n=1,2,3,…}, can be written as {aba, aabbaa, aaabbbaaa,aaaabbbbaaaa,…}
  • Example: The language factorial, of strings defined over Σ=1,2,3,4,5,6,7,8,9Σ={1,2,3,4,5,6,7,8,9} i.e. {1,2,6,24,120,…}

  • Example: The language FACTORIAL, of strings defined over Σ=aΣ={a}, as

    • an!:n=1,2,3,…{a^{n!} : n=1,2,3,…}, can be written as {a,aa,aaaaaa,…}. It is to be noted that the language FACTORIAL can be defined over any single letter alphabet.
  • Example: The language DOUBLEFACTORIAL, of strings defined over Σ=a,bΣ={a, b}, as

    • an!bn!:n=1,2,3,…{a^{n!}b^{n!} : n=1,2,3,…}, can be written as {ab, aabb, aaaaaabbbbbb,…}
  • Example: The language SQUARE, of strings defined over Σ=aΣ={a}, as

    • an2:n=1,2,3,…{a^{n^2} : n=1,2,3,…}, can be written as {a, aaaa, aaaaaaaaa,…}
  • Example: The language DOUBLESQUARE, of strings defined over Σ=a,bΣ={a,b}, as

    • an2bn2:n=1,2,3,…{a^{n^2} b^{n^2} : n=1,2,3,…}, can be written as {ab, aaaabbbb, aaaaaaaaabbbbbbbbb,…}
  • Example: The language PRIME, of strings defined over Σ=aΣ={a}, as

    • ap:p is prime{a^p : p \text{ is prime}}, can be written as {aa,aaa,aaaaa,aaaaaaa,aaaaaaaaaaa…}

An Important language

  • PALINDROME: The language consisting of ΛΛ and the strings s defined over ΣΣ such that Rev(s)=s. It is to be denoted that the words of PALINDROME are called palindromes.
  • Example: For Σ=a,bΣ={a,b},
    • PALINDROME={ΛΛ , a, b, aa, bb, aaa, aba, bab, bbb, …}