Study of Theory of Automata

Automata Theory is a branch of computer science that deals with designing abstract computing models having a sequence of operations. With the help of that model, it will be easy to write algorithms and convert that into machines.

Automata − What is it?

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.

An automaton with a finite number of states is called a Finite Automaton.

The formal definition of a Finite Automaton

An automaton can be represented by a 5-tuple (Q, ∑, δ, q0, F), where −

Q is a finite set of states.

∑ is a finite set of symbols, called the alphabet of the automaton.

δ is the transition function.

q0 is the initial state from where any input is processed (q0 ∈ Q).

F is a set of final states/states of Q (F ⊆ Q). 

Every Automaton fulfills the three basic requirements.

·    It consists of some essential features as in real computers. It has a mechanism for reading input. The input is assumed to be a sequence of symbols

over a given alphabet and is placed on an input tape(or written on an input file). The simpler automata can only read the input one symbol at a time from left to right but not change. Powerful versions can both read (from left to right or right to left) and change the input.

·    The automaton can produce output of some form. If the output in response to an input string is binary (say, accept or reject), then it is called an accepter. If it produces an output sequence in response to an input sequence, then it is called a transducer (or automaton with output).

·     The automaton may have a temporary storage, consisting of an unlimited number of cells, each capable of holding a symbol from an alphabet (which may be different from the input alphabet). The automaton can both read and change the contents of the storage cells in the temporary storage. The accusing capability of this storage varies depending on the type of the storage.

·         The most important feature of the automaton is its control unit, which can be in any one of a finite number of interval states at any point. It can change state in some defined manner determined by a transition function. 

Diagrammatic representation of generic automation.

Related Terminologies

Alphabet

Definition − An alphabet is any finite set of symbols.

Example − ∑ = {a, b, c, d} is an alphabet set where ‘a’, ‘b’, ‘c’, and ‘d’ are alphabets.

String

Definition − A string is a finite sequence of symbols taken from ∑.

Example − ‘cabcad’ is a valid string on the alphabet set ∑ = {a, b, c,d} 

Length of a String

Definition − It is the number of symbols present in a string. (Denoted by |S|).

Examples −If S=‘cabcad’, |S|= 6If |S|= 0, it is called an empty string (Denoted by λ or ε)

Kleene Star

Definition − The set ∑* is the infinite set of all possible strings of all possible lengths over ∑ including λ.

Representation − ∑* = ∑0 ∪ ∑1 ∪ ∑2 ∪…….

Example − If ∑ = {a, b}, ∑*= {λ, a, b, aa, ab, ba, bb,………..}

Kleene Closure/Plus

Definition − The set ∑+ is the infinite set of all possible strings of all possible lengths over ∑ excluding λ.

Representation − ∑+ = ∑0 ∪ ∑1 ∪ ∑2 ∪…….∑+ = ∑* − { λ }

Example − If ∑ = { a, b } , ∑+ ={ a, b, aa, ab, ba, bb,………..}

Language

Definition − A language is a subset of ∑* for some alphabet ∑. It can be finite or infinite.

Example − If the language takes all possible strings of length 2 over ∑ = {a, b}, then L = { ab, bb, ba, bb}

 Also, Study about: 

• Mealy Machine
• Moore Machine
• Rice Theorem
• Brief about Turing Machine
• Multi Dimension Turing Machine
• Multiple Turing Machine
• Parikh Theorem in TOC
• Parse Tree or Derivation Tree
• What do you Understand by Derivation
• MyHill Nerode Theorem
• Minimize Myhill Nerode Theorem
• Push Down Automata
• Know Where we use Automata
• What do you understand by Derivation of Grammar
• What is Context-free Grammar
• Example based on CFG
• Regular Expression in TOC
• What is Two-way infinite Turing machine?
• Example to generate Parse tree from the given grammar

Also Read, some interview tips

• Why Should I Hire You?
• What are your weaknesses?
• What are your greatest strengths?
• Tell me about yourself.
• What's the reason behind leaving your current position at your company?
• Do You Know how the power of Keywords impacts on Resume?
• Top 8 Proofreading Tips and Techniques in 2022.
• Top Ten Technical Resume Writing Tips in 2022.
• Tips for your resume before you get entry to Job Market
• What Questions you can ask HR during the Interview.
• How to make an impressive resume?
• Best Resume writing Technique.
• What Questions you can ask HR during the Interview.