Theory of Automata

The theory of automata is the study of abstract machines and computation problems. The computation problems can be solved using these abstract machines. The abstract machine is called the automata or automaton.

Circles and arrows represent automata. Circles represent states, and arrows represent transitions. Automata takes some input strings as input, and this input goes through some states and may be entered in the final state.

Basic Elements – Theory of Automata

Grammar defines production rules, which generate strings (made from input symbols). These strings form a language, which can be accepted or rejected by an automata machine.

Elements in Theory of Automata

The following are some essential elements of the theory of Automata.

1. Grammar

A grammar is a formal set of rules used to generate strings in a language. It includes:

  • A start symbol
  • Non-Terminals (variables)
  • Terminals (alphabet symbols)
  • Production rules

Example:

Let the grammar be:

  • Start Symbol: S

  • Terminals: a, b

  • All Production Rules:

    • S → aS

    • S → bS

    • S → a

Can represented as S → aS | bS | a

Production rules are the specific rewriting rules in a grammar. They tell how to replace non-terminals with terminals or other non-terminals.

 From above grammar, rules are:

  • S → aS

  • S → bS

  • S → a

These allow generating strings like:

  • a

  • aa (S → aS → aa)

  • aba (S → aS → abS → aba)

Grammar is commonly used to represent a Set of Production Rules with the letter ‘P’.

Note: In all Production rules, P : S → aS | bS | a. Where S → a is one the production rule.

The followings are the major types of  grammar in Automata

  • Type-3: Regular Grammar – Used by Finite Automata to generate Regular Languages.

  • Type-2: Context-Free Grammar (CFG) – Used by Pushdown Automata to generate Context-Free Languages.

  • Type-1: Context-Sensitive Grammar (CSG) – Used by Linear Bounded Automata to generate Context-Sensitive Languages.

  • Type-0: Unrestricted Grammar – Used by Turing Machines to generate Recursively Enumerable Languages.

2. Input Strings

Input strings are sequences of terminal symbols (like a, b) that are derived by applying production rules starting from the start symbol. It is a collection of some symbols from the Sigma (∑). The symbol ‘W’ denotes the string.

String Examples (from the Grammar above):

  • a

  • aa

  • ababa

  • bba

These are input strings we may feed into an automaton for testing.

Important: Sigma (∑) contains a finite set of symbols known as an alphabet. Symbols involve letters, the alphabet, or any picture. Strings are made from input symbols (∑).

Examples: ∑ = {a, b} , ∑ = {A, B, C, D} , ∑ = {0, 1, ….., 5]  

If ∑ = {x, y}, then various strings that can be generated from ∑ are {x, y, xxx, xyxy, yy, xyy, …..,}.

An empty string, also known as an epsilon string, is a string that contains no symbols or has zero occurrences of symbols. Symbol ‘ε’ denotes the epsilon string. A string’s length refers to the number of characters it contains. Symbol ‘|w|’ denotes the length of that string. If the string is w= 010, its length is 3.

3. Language

A language is the set of all valid strings that can be generated by a grammar. Grammar uses production rules to create the set of strings. 

Note: Languages in automata are classified into four major types: Regular, Context-Free, Context-Sensitive, and Recursively Enumerable, based on the Chomsky Hierarchy.

Example 01:

The language L = { all strings over a and b that end in a }

So:

  • Valid strings (in the language): a, aa, aba, bba

  • Invalid strings: b, ab, bb

Example: 02

Language (L) = {Set of string of length 2} = {xx, yy, xy, yx}        //  Finite Language

Example: 03

L2 = {Set of all strings starts with ‘x’} = {x, xx, x, xyy, xyyyy, xyxyxyyyx, ………,}      //  Infinite Language

4. Automata Machine

An automaton (like a DFA or NFA) is a state machine that recognizes the language by processing input strings and decides whether they belong to a language.

It consists of:

  • States
  • Transitions based on input symbols
  • A start state
  • Accepting (final) state(s)

The automaton takes each input string and processes it through states. If it ends in an accepting state, the string is accepted; otherwise, it’s rejected.

Note: Some examples of automata machines are Finite Automaton (FA),  Pushdown Automaton (PDA), Linear Bounded Automaton (LBA), Turing Machine (TM), Moore machine, Mealy machine etc.

Validation of an Automata Machine



  • An automaton is designed to recognize a language (a set of valid strings).

  • To validate that the automaton is correct, we test it using strings:

    • It should accept all strings in the language.

    • It should reject all strings not in the language.

So, we validate the machine by checking how it behaves on many test strings — both valid and invalid — based on the definition of the target language.

 Example:

Let the language L = all binary strings that end in 1.

We can validate the DFA for this language using strings like:

  • "1" → Should be accepted

  • "101" → Accepted

  • "100" → Rejected

  • "" (empty string) → Rejected

If the DFA accepts all strings in L and rejects all others, then it is valid for language L.

Theory of Automata Notations

The following diagram represents the notations used in automata theory.

Notations in Theory Of Automata

Important: Languages are generated according to their grammar and accepted or rejected by automata machines. Automata are abstract machines that accept or reject regular languages.

Note: “It is possible to express all regular languages using Regular Expressions.”

Types of Automata Machines

The following table presents information about different types of automata and their respective recognized languages and computational abilities. Each automaton type ranges from regular to ω-regular language classes. The purpose of the table is to demonstrate the varying computational capacities of different automata models.

Automata Machine Recognized Languages Computational Power
Finite Automaton (FA) Regular Languages Limited to Regular Languages
Two-Way Finite Automaton Regular Languages Same as Finite Automaton
Mealy Machine Output depends on state and input Limited to Regular Languages
Moore Machine Output depends only on the state Limited to Regular Languages
Pushdown Automaton (PDA) Context-Free Languages More powerful than Finite Automaton
Linear Bounded Automaton (LBA) Context-Sensitive Languages More powerful than PDA
Nested Stack Automaton Certain types of nested structures More expressive than PDAs
Register Machine Integer functions Turing-equivalent
Turing Machine (TM) Recursively Enumerable Languages The most powerful model of computation
Multi-Tape Turing Machine Recursively Enumerable Languages Same as the Turing Machine
Non-deterministic Turing Machine (NDTM) Recursively Enumerable Languages Same as the Turing Machine
Deterministic Büchi Automaton ω-limit Languages Recognizes languages with infinite words satisfying Büchi acceptance condition
Nondeterministic Büchi Automaton ω-Regular Languages Recognizes languages with infinite words satisfying Büchi acceptance condition
Weighted Automaton Weighted Languages Assign weights to infinite words
Rabin Automaton, Streett Automaton, Parity Automaton, Muller Automaton ω-Regular Languages Recognize various classes of ω-regular languages

Applications Theory of Automata

Following are the applications of thoery of automata 

  • Compiler Design: Utilizes automata theory for lexical analysis and parsing in compiler construction.
  • Parsing and Syntax Analysis: Uses context-free grammars and pushdown automata for analyzing syntax in compilers.
  • Lexical Analysis: Applies regular expressions and finite automata to identify tokens in programming language source code.
  • Natural Language Processing (NLP): Involves language recognition and syntax analysis for applications like speech recognition.
  • Software Engineering: Utilizes automata for specifying and verifying correctness in software systems.
  • Model Checking: Verifies system specifications to ensure correctness in hardware and software.
  • Network Protocol Design: Uses finite state machines to model and analyze network protocol behavior.
  • DNA Computing: Applies automata concepts for solving computational problems using DNA strands.
  • Formal Verification: Uses automata for verifying correctness in hardware and software systems.
  • Regular Expressions in Text Processing: Widely used for searching and data extraction tasks.
  • Databases: Applies finite automata and regular expressions for query processing and pattern matching.
  • VLSI Design: Utilizes automata theory in modeling and optimizing sequential circuits in VLSI.
  • Robotics: Implements finite state machines to model and control robot behavior based on sensory input.

"Your Support, Our Priority"

"We Make It Easy"