Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction 
2.
Basic Terminologies of Automata Theory
3.
FAQs-
4.
Key takeaways-
Last Updated: Mar 27, 2024

Introduction of Automata Theory

Author Riya
3 upvotes
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction 

Theoretical Computer Science is a branch of computer science and mathematics in which we study mathematical aspects of computer science. 

One of the branches of theoretical computer science is the ‘Theory of Computation’, which deals with what are the problems that can be solved using an algorithm on a model of computation and also up to what extent and with what accuracy these problems can be solved. 

This field of ‘Theory of Computation’ is divided into three major branches and ‘Automata Theory’ is one of them.

Automata theory is the branch of theoretical computer science that focuses on the study of computational problems that can be solved by machines called automata. 

Automata takes strings as inputs and this input goes through predetermined operations called states.  Automata are used to study how the machines compute and solve the problems.

Now, let’s learn about the basic terminologies that are used in automata theory.

Also see, Turing Machine in TOC.

 

You can also read about Greibach Normal Form here.

Basic Terminologies of Automata Theory

In this section, we will discuss the basic terminologies that are frequently used in Automata Theory. 

The following terminologies are important in Automata Theory:

1. Symbols
Symbols are individual elements which are the basic building blocks, and can be any picture, letter or alphabet. Examples: 0, 1, a, b, .. etc.

2. Alphabets
Alphabets are a set of symbols denoted by ∑.

Example: 

∑ = {A, B, C} is an alphabet set where ‘A’, ‘B’, and ‘C’ are symbols

∑ = {1, 2, 3} is an alphabet set where ‘1’, ‘2’, and ‘3’ are symbols

3. String
String is a finite sequence of symbols from any alphabet. It is generally denoted by ‘w’ and the length of the string is denoted by |w|.

Example:

For an alphabet ∑ = {A, B, C}, the following strings can be generated through this set - 

{“AAA”, “A”, “AA”, “AB”, ……….}

          Note: An empty string i.e. the string with zero occurrences of symbols is represented by ε.

4. Language
A language is a set of strings selected from all the strings that can be generated from a given alphabet set. It can be finite or infinite.

Suppose an alphabet  ∑ = {a, b, c}

Set of strings from this alphabet = {“a”, “aa”, “aaa”, “b”, “bb”, “ab”, ………..}

An example of finite language is

Language1 = {set of strings of length 1}

                     = {‘a’, ‘b’, ‘c’}

An example of infinite language is

Language2 = {set of strings containing only ‘a’}

                     = {‘a’, “aa”, “aaa”, “aaaa” ………}

5. Kleene star
Keelene star is an unary operator on a set of strings that gives an infinite set of all possible strings with all possible lengths including zero-length string (ε). It is denoted by  ∑* .

Suppose  ∑ = {a, b, c}

Then,  ∑* = {ε,  a, b, c, aa, bb, ……..}

6. Kleene Closure
Keelene Closure is an unary operator on a set of strings that gives an infinite set of all possible strings with all possible lengths excluding zero-length strings (ε). It is denoted by  + .

Suppose  ∑ = {a, b, c}

Then,  + = {ε,  a, b, c, aa, bb, ……..}

Also See, Moore Machine

Also read, Arden's theorem

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

FAQs-

1. What is Theory of Computation?

Theory of computation is a branch of theoretical computer science which deals with what are the problems that can be solved using an algorithm on a model of computation and also up to what extent and with what accuracy these problems can be solved. 

2.What is Automata Theory?

Automata theory is the branch of theoretical computer science that focuses on the study of computational problems that can be solved by machines called automata.

Key takeaways-

This article discussed the introduction  of “Automata theory”. If you think that this blog helped you share it with your friends!. 

Check out this article - Converting NFA to DFA

To be more confident in data structures and algorithms, try out our DS and Algo Course.

Until then, All the best for your future endeavors, and Keep Coding.

Previous article
Introduction to Automata
Next article
Finite State Machine
Live masterclass