Automata in Theory of Computing

What is Automata ?

We know that, language is a collection of strings, which can be classified into two types. Finite and Infinite. Finite language means which have fixed number of strings and can be counted. Infinite language means infinite number of strings and can not be counted. 

Suppose , given an alphabet, Σ = {a,b} and we have to construct a language for two different cases.

Case 1 , where length is 2 and Case 2 where length is at least 1 a.

Language in case 1 : {aa,ab,ba,bb}, which is a finite language.

Language in case 2 : {a,aa,aaa,aaaa,abba,abab,ba,baba,…………………………… }, which is an infinite language.

Now, there is a given string w ={ba} and we have to determine if this string is part of the language or not.  The first way is to store the strings of language in the memory and then check one by one, if the given string is part of the language or not.

• In case of  Finite language, we have fixed number of strings, so we can store them in the memory and match the given string one by one to see whether it is equal or not.
• In case of Infinite language, we have infinite number of strings and it is not possible to store infinite number of strings in the memory. Hence, it is not possible to match the given string.

So to solve this problem we use the concept of Automata.

Automata is a mathematical model or machine that process inputs by moving through a finite set of states following predefined rules to produce outputs.

Basic terminologies – 

1. States : set of configuration that the machine can be in.
2. Input/Output : Sequence of symbols that the machine can process.

Automata are primarily used to accept or reject inputs by transitioning between states. It is a foundational concept in the theory of computation, designed to model how systems solve problems, recognize patterns (formal languages), and determine the capabilities and limitations of computers.

Applications of Automata – 

• Compiler Design – recognizing syntax in programming languages
• Natural Language Processing – speech recognition and information retrieval
• AI and Machine Learning – Modelling intelligent agents
• Network Protocols – analyzing communication patterns

Types of Automata

1. Finite Automata(FA) – Simple machines with limited memory, used for pattern matching (e.g., regex).
2. Pushdown Automata(PDA) – More complex machines incorporating a stack, used for parsing context-free languages.
3. Linear Bound Automata
4. Turing Machines – The most powerful model, defining what is computable