Open In App

Automata Tutorial

Last Updated : 20 Aug, 2024
Summarize
Comments
Improve
Suggest changes
Like Article
Like
Save
Share
Report
News Follow

Automata theory is a branch of the theory of computation. It deals with the study of abstract machines and their capacities for computation. An abstract machine is called the automata. It includes the design and analysis of automata, which are mathematical models that can perform computations on strings of symbols according to a set of rules.

Theory of computation is the branch of computer science that studies the nature and ranges of computation. It includes analysis and design of algorithms computation systems, formal languages, automata theory, compatibility theory, and complexity theory.

In this Automata Tutorial, you’ll learn all the basic to advanced topics like Regular languages and finite automata, Context free Grammar and Context-free language, turning machines, etc.

Table of Content

Recent Articles on Theory Of Computation

Automata – Introduction

  1. Introduction of Theory of Computation
  2. Chomsky Hierarchy
  3. Applications of various Automata

Regular Expression and Finite Automata

  1. Finite Automata Introduction
  2. Arden’s Theorem and Challenging Applications | Set 2
  3. L-graphs and what they represent
  4. Hypothesis (language regularity) and algorithm (L-graph to NFA)
  5. Regular Expressions,Regular Grammar and Regular Languages
  6. How to identify if a language is regular or not
  7. Arden’s Theorem
  8. Finite Automata from Regular Expressions
  9. Star Height of Regular Expression and Regular Language
  10. Generating regular expression from finite automata
  11. Designing Deterministic Finite Automata (Set 1)
  12. Designing Deterministic Finite Automata (Set 2)
  13. DFA for Strings not ending with “THE”
  14. DFA of a string with at least two 0’s and at least two 1’s
  15. DFA for accepting the language L = { anbm | n+m=even }
  16. DFA machines accepting odd number of 0’s or/and even number of 1’s
  17. DFA of a string in which 2nd symbol from RHS is ‘a’
  18. Union process in DFA
  19. Concatenation process in DFA
  20. DFA in LEX code which accepts even number of zeros and even number of ones.
  21. NFA to DFA Conversion
  22. Program to Implement NFA with epsilon move to DFA Conversion
  23. Minimization of DFA
  24. Reversal process in DFA
  25. Complementation process in DFA
  26. Kleene’s Theorem Part-1
  27. MEALY and MOORE Machines
  28. Difference between Mealy machine and Moore machine

>> Practice problems on finite automata
>> Practice problems on finite automata | Set 2
>> Quiz on Regular Languages and Finite Automata

CFG (Context Free Grammar)

  1. Relationship between grammar and language
  2. Simplifying Context Free Grammars
  3. Closure Properties of Context Free Languages(CFL)
  4. Union & Intersection of Regular languages with CFL
  5. Converting Context Free Grammar to Chomsky Normal Form
  6. Converting Context Free Grammar to Greibach Normal Form
  7. Pumping Lemma
  8. Check if the language is Context Free or Not
  9. Ambiguity in Context Free Grammar
  10. Operator grammar and precedence parser
  11. Context-sensitive Grammar (CSG) and Language (CSL)

PDA (Pushdown Automata)

  1. Pushdown Automata
  2. Pushdown Automata Acceptance by Final State
  3. Construct Pushdown Automata for given languages
  4. Construct Pushdown Automata for all length palindrome
  5. Detailed Study of PushDown Automata
  6. NPDA for accepting the language L = {an bm cn| m,n>=1}
  7. NPDA for accepting the language L = {an bn cm | m,n>=1}
  8. NPDA for accepting the language L = {anbn | n>=1}
  9. NPDA for accepting the language L = {am b(2m) | m>=1}
  10. NPDA for accepting the language L = {am bn cp dq| m+n=p+q ; m,n,p,q>=1}
  11. Construct Pushdown automata for L = {0n1m2m3n | m,n ? 0}
  12. Construct Pushdown automata for L = {0n1m2(n+m) | m,n ? 0}
  13. NPDA for accepting the language L = {ambnc(n+m) | m,n ? 1}
  14. NPDA for accepting the language L = {amb(n+m)cn| m,n ? 1}
  15. NPDA for accepting the language L = {a2mb3m | m ? 1}
  16. NPDA for accepting the language L = {amb(2m+1) | m ? 1}
  17. NPDA for accepting the language L = {aibjckdl | i==k or j==l,i>=1,j>=1}
  18. Construct Pushdown automata for L = {a(2*m)c(4*n)dnbm | m,n ? 0}
  19. Construct Pushdown automata for L = {0n1m2(n+m) | m,n ? 0}
  20. NPDA for L = {0i1j2k | i==j or j==k ; i , j , k >= 1}
  21. NPDA for accepting the language L = {anb(2n) | n>=1} U {anbn | n>=1}
  22. NPDA for the language L ={w?{a,b}*| w contains equal no. of a’s and b’s}

>> Quiz on Context Free Languages and Pushdown Automata

Turing Machine

  1. Turing Machine
  2. Turing Machine for addition
  3. Turing machine for subtraction | Set 1
  4. Turing machine for multiplication
  5. Turing machine for copying data
  6. Construct a Turing Machine for language L = {0n1n2n | n?1}
  7. Construct a Turing Machine for language L = {wwr | w ? {0, 1}}
  8. Construct a Turing Machine for language L = {ww | w ? {0,1}}
  9. Construct Turing machine for L = {anbma(n+m) | n,m?1}
  10. Construct a Turing machine for L = {aibjck | i*j = k; i, j, k ? 1}
  11. Turing machine for 1’s and 2’s complement
  12. Recursive and Recursive Enumerable Languages
  13. Turing Machine for subtraction | Set 2
  14. Halting Problem
  15. Theory of Computation | Applications of various Automata
  16. Turing Machine as Comparator

>> Quiz on Turing Machines and Recursively Enumerable Sets

Decidability

  1. Decidable and undecidable problems
  2. Decidability
  3. Undecidability and Reducibility
  4. NP-Completeness | Set 1 (Introduction)
  5. Proof that Hamiltonian Path is NP-Complete
  6. Proof that vertex cover is NP complete
  7. Computable and non-computable problems

>> Quiz on Undecidability

Quick Links :

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.



K
kartik
News
Improve
Next Article
Introduction of Theory of Computation

Similar Reads

Difference Between Pushdown Automata and Finite Automata
Two important computational models in automata theory that are used to identify various language kinds are Pushdown Automata (PDA) and Finite Automata (FA). Both automata process strings as input and switch between states according to pre-established rules. Still, their memory capacities account for the majority of the variance. Pushdown Automata h
5 min read
Automata Theory | Set 3
Following questions have been asked in GATE CS 2011 exam. 1) The lexical analysis for a modern language such as Java needs the power of which one of the following machine models in a necessary and sufficient sense? (A) Finite state automata (B) Deterministic pushdown automata (C) Non-deterministic pushdown automata (D) Turing machine Answer (A) Lex
2 min read
Automata Theory | Set 4
Following questions have been asked in GATE CS 2011 exam. 1) Let P be a regular language and Q be context-free language such that Q ⊆ P. (For example, let P be the language represented by the regular expression p*q* and Q be {pnqn|n ∈ N}). Then which of the following is ALWAYS regular? (A) P ∩ Q (B) P - Q (C) ∑* - P (D) ∑* - Q
2 min read
Automata Theory | Set 5
Following questions have been asked in GATE CS 2009 exam. 1) S --> aSa| bSb| a| b ;The language generated by the above grammar over the alphabet {a,b} is the set of (A) All palindromes. (B) All odd length palindromes. (C) Strings that begin and end with the same symbol (D) All even length palindromes. Answer (B) The strings accepted by language are
3 min read
Construct Pushdown Automata for given languages
Prerequisite - Pushdown Automata, Pushdown Automata Acceptance by Final State A push down automata is similar to deterministic finite automata except that it has a few more properties than a DFA.The data structure used for implementing a PDA is stack. A PDA has an output associated with every input. All the inputs are either pushed into a stack or
4 min read
Generating regular expression from Finite Automata
Prerequisite - Introduction of FA, Regular expressions, grammar and language, Designing FA from Regular Expression There are two methods to convert FA to the regular expression: 1. State Elimination Method:Step 1 - If the start state is an accepting state or has transitions in, add a new non-accepting start state and add an €-transition between the
3 min read
Pushdown Automata Acceptance by Final State
We have discussed Pushdown Automata (PDA) and its acceptance by empty stack article. Now, in this article, we will discuss how PDA can accept a CFL based on the final state. Given a PDA P as: P = (Q, Σ, Γ, δ, q0, Z, F) The language accepted by P is the set of all strings consuming which PDA can move from initial state to final state irrespective of
4 min read
Construct Pushdown Automata for all length palindrome
A Pushdown Automaton (PDA) is like an epsilon Non deterministic Finite Automata (NFA) with infinite stack. PDA is a way to implement context free languages. Hence, it is important to learn, how to draw PDA. Here, take the example of odd length palindrome: Que-1: Construct a PDA for language L = {wcw' | w={0, 1}*} where w' is the reverse of w. Appro
6 min read
Practice problems on finite automata
Que-1: Draw a deterministic and non-deterministic finite automate which accept 00 and 11 at the end of a string containing 0, 1 in it, e.g., 01010100 but not 000111010. Explanation - Design a DFA and NFA of a same string if input value reaches the final state then it is acceptable otherwise it is not acceptable. NFA of the given string is as follow
2 min read
Practice problems on finite automata | Set 2
Que-1: Draw a deterministic and non-deterministic finite automate which either starts with 01 or end with 01 of a string containing 0, 1 in it, e.g., 01010100 but not 000111010. Explanation - Draw a DFA and NFA of same language whose strings only reach to the final state containing either 01 at start or at the end. If anything else is come then com
3 min read
Construct Pushdown automata for L = {0n1m2m3n | m,n ≥ 0}
Prerequisite - Pushdown automata, Pushdown automata acceptance by final state Pushdown automata (PDA) plays a significant role in compiler design. Therefore there is a need to have a good hands on PDA. Our aim is to construct a PDA for L = {0n1m2m3n | m,n ≥ 0} Examples - Input : 00011112222333 Output : Accepted Input : 0001122233 Output : Not Accep
3 min read
Construct Pushdown automata for L = {a(2*m)c(4*n)dnbm | m,n ≥ 0}
Prerequisite – Pushdown automata, Pushdown automata acceptance by final state PDA plays a very important role in task of compiler designing. That is why there is a need to have a good practice on PDA. Our objective is to construct a PDA for L = {a(2*m)c(4*n)dnbm | m,n ≥ 0} Examples - Input: aaccccdb Output: Accepted Input: aaaaccccccccddbb Output:
3 min read
Construct Pushdown automata for L = {0n1m2(n+m) | m,n ≥ 0}
Prerequisite - Pushdown automata, NPDA for accepting the language L = {ambnc(m+n) | m,n ≥ 1} PDA plays a very important role in task of compiler designing. That is why there is a need to have a good practice on PDA. Our objective is to construct a PDA which accepts a string of the form {(0^n)(1^m)(2^(n+m))} Example- Input: 00001112222222 Output: Ac
2 min read
Designing Finite Automata from Regular Expression (Set 6)
Prerequisite: Finite automata, Regular expressions, grammar and language, Designing finite automata from Regular expression (Set 5) In the below article, we shall see some Designing of Finite Automata form the given Regular Expression- Regular Expression 1: Regular language, L1 = a(a+b)* The language of the given RE is, {aaa, aba, baa, bba} Strings
3 min read
Finite Automata with Output (Set 6)
Prerequisite: Mealy and Moore Machines, Difference between Mealy machine and Moore machine In this article, we will see some designing of Finite Automata with Output, i.e., Moore and Mealy machines. Problem: Construction of the machines that take set of all string over {0, 1} as input and produce 'A' as output if the input contains '101' as the sub
2 min read
Finite Automata with Output (Set 5)
Prerequisite: Mealy and Moore Machines, Difference between Mealy machine and Moore machine In this article, we will see some designing of Finite Automata with Output i.e, Moore and Mealy machines. Problem: Construction of the machines that take set of all string over {0, 1} as input and produce 'A' as output if the input contains '1' as the substri
2 min read
Construct Pushdown automata for L = {0m1(n+m)2n | m,n ≥ 0}
Prerequisite – Pushdown automata, NPDA for accepting the language L = {amb(n+m)cm | m, n >= 1} Problem: Construct Pushdown automata for L = {0m1(n+m)2n | m,n ≥ 0} Example: Input: 011122 Output: Accepted Input: 00000112222 Output: Not Accepted Approach used in this PDA – There can be four cases while processing the given input string. Case 1-
2 min read
Construct Pushdown automata for L = {0(n+m)1m2n | m, n ≥ 0}
Prerequisite – Pushdown automata Problem: Construct Pushdown automata for L = {0(n+m)1m2n | m, n ≥ 0} Similar PDA's- This PDA seems to be similar to PDA of S2 = {0m1(n+m)2n} but the production is different. S2 will produce output which have no of 1's equal to the sum of no of 0's and 2's, while S1 does not. This PDA seems to be similar to PDA of
3 min read
Designing Deterministic Finite Automata (Set 5)
Prerequisite: Designing finite automata In this article, we will see some designing of Deterministic Finite Automata (DFA). Problem-1: Construction of a minimal DFA accepting set of strings over {a, b} in which every 'a' is followed by a 'bb'. Explanation: The desired language will be like: L1 = {ε, abb, abbabb, bbbbabb, abbabbabbabbabbbb,
3 min read
Designing Deterministic Finite Automata (Set 9)
Prerequisite: Designing finite automata In this article, we will see some designing of Deterministic Finite Automata (DFA). Problem-1: Construction of a minimal DFA accepting a set of strings over {a, b} in which {abwa / wε{a, b}*}. Here 'w' is the substring containing alphabets over any number of 'a' and 'b' ranging from zero to infinity.
4 min read
Designing Deterministic Finite Automata (Set 6)
Prerequisite: Designing finite automata In this article, we will see some designing of Deterministic Finite Automata (DFA). Problem-1: Construction of a minimal DFA accepting set of strings over {a, b} in which anbm, where n and m is greater than or equal to 1. Explanation: The desired language will be like: L1 = {ab, aab, abb, aabb, aaabbb, aaabbb
3 min read
Finite Automata with Output (Set 3)
Prerequisite: Mealy and Moore Machines, Difference between Mealy machine and Moore machine In this article, we will see some designing of Finite Automata with Output i.e, Moore and Mealy machines. Problem: Construction of the machines that take set of all string over {a, b} as input and count number of substring 'a'. That is here we have, Ε
2 min read
Automata Theory | Set 7
These questions for practice purpose for GATE CS Exam. Ques-1: Consider L= {(TM) | TM is the Turing machine that halts on all input and L(TM)= L' for some undecidable language L'}. Here, (TM) is the encoding of a Turing machine as a string over alphabet {0, 1} then L is: (A) decidable and recursively enumerable (B) decidable and recursive (C) decid
3 min read
Automata Theory | Set 8
These questions for practice purpose for GATE CS Exam. Ques-1: Which one of the following language is Regular? (A) {wxwR | w,x ∈ (a+b)+} (B) {wxwR | w ∈ (a+b)*, x ∈ {a,b}} (C) {wwRx | w,x ∈ (a+b)+} (D) {wwR | w ∈ (a+b)*} Explanation: (A) It is correct, since this language can form regular expression which is {{ a(a + b)+a } + {b(a + b)+b}}, i.e., s
2 min read
Designing Finite Automata from Regular Expression (Set 2)
Prerequisite: Finite automata, Regular expressions, grammar and language. Designing finite automata from Regular expression In the below article, we shall see some Designing of Finite Automata form the given Regular Expression- Regular Expression 1: Φ (Phi). The language of the given RE is L1 = {} i.e, empty string. Its finite automata will be
3 min read
Automata Theory | Set 9
These questions for practice purpose for GATE CS Exam. Ques-1: Consider the following two statements with respect to Countability: Statement-1: If X union of 'Y' is uncountable, then both set 'X' and set 'Y' must be uncountable. Statement-2: The Cartesian product of two countable sets 'X' and 'Y' is countable. Which of the following option is true
3 min read
Designing Finite Automata from Regular Expression (Set 3)
Prerequisite: Finite automata, Regular expressions, grammar and language, Designing finite automata from Regular expression (Set 2) In the below article, we shall see some Designing of Finite Automata form the given Regular Expression. Regular Expression 1: 'ab*' ('a' followed by any number of 'b'). The language of the given RE is, L1 = {a, ab, abb
3 min read
Designing Finite Automata from Regular Expression (Set 4)
Prerequisite: Finite automata, Regular expressions, grammar and language, Designing finite automata from Regular expression (Set 3) In the below article, we shall see some Designing of Finite Automata form the given Regular Expression- Regular Expression 1: Regular language, L1 = (a+b)(a+b) The language of the given RE is, {aa, ab, ba, bb} Length o
3 min read
Automata Theory | Set 10
These questions for practice purpose of GATE CS Exam. Ques-1: Consider the following statements: X: For any language either a language L or its complement L' must be finite.Y: DFA for language which contains epsilon must have initial state as final state.Z: Non-deterministic finite automata is more powerful than deterministic finite automata. Which
3 min read
Designing Finite Automata from Regular Expression (Set 5)
Prerequisite: Finite automata, Regular expressions, grammar and language, Designing finite automata from Regular expression (Set 4) In the below article, we shall see some Designing of Non-deterministic Finite Automata form the given Regular Expression- As NFA can be changed to corresponding DFA. Regular Expression 1: Regular language, L1 = ((a+b)(
3 min read
Article Tags :
three90RightbarBannerImg
We use cookies to ensure you have the best browsing experience on our website. By using our site, you acknowledge that you have read and understood our Cookie Policy & Privacy Policy
Lightbox