Frequently Asked Questions (FAQ)

1.  Construct NFA for the language: L= {w|w is in the form of ‘x01y’ for some strings x and y consisting of 0’s and 1’s}.

2.  Illustrate the construction of Non Deterministic Finite Automata for the Regular Expression: (a+b)*a

3.  Draw the transition diagram for NFA which accepts all strings with two consecutive 0’s

4.  Construct the regular expression for the language over the set S={0,1} that can have a set of all strings containing no three consecutive 0’s

5.  Construct NFA over the alphabet Σ={a,b} for the language having a set of strings formed using either 101 or 110 as substring.

6.  Constructure the Finite Automata using 5-tuple notation for the recognizing a set of strings that can have 1 followed immediately by 00

7.  Draw the ε-NFA and compute the εclosure of each state. Identify the subsets of starting state in DFA.

8.  How many states will the DFA equivalent of NFA with n states have in the worst case? Justify.

9.  Construct a CFG to generate the binary strings that are Palindromes ex: 010, 00100, 101, 11011

10.  Identify the language generated by the following CFG: S-->Aab; A-->Aab|b

Continue reading →

Conversion of e-NFA to DFA

Problems Solved during Class Room Teaching

Problem 1:

Problem 2:

Continue reading →

Tutorial-2 on RE & CFG

Tutorial-2 on RE & CFG

Q1.  Illustrate the construction of Non Deterministic Finite Automata for the Regular Expression: (a+b)*a

Q2.  Construct the regular expression for the language over the set S={0,1} that can have a set of all strings containing no three consecutive 0’s

Q3.  Construct a CFG to generate the binary strings that are Palindromes ex: 010, 00100, 101, 11011

Q4.  Identify the language generated by the following CFG:  S-->Aab; A-->Aab|b

Q5.  Construct the NFA for the regular expression r = ((01+10)*00)*

Q6. Constructure the Finite Automata using 5-tuple notation for the regular expression 1*01(0+11)*

Continue reading →

Tutorial-1 on Automata Theory

Tutorial-1 on Finite Automata

Q1.  For the given NFA which of the following is the equivalent DFA:

Q2.  Consider the following NFA and answer the following:

        a) Compute the ε-closure of each state.

        b) Convert the automaton to a DFA.

Q3.  Consider the following ε-NFA and do the following:

      a) Compute the ε-closure of each state.

      b) Convert the automaton to a DFA.

Q4.  Constructure the Finite Automata from the following 5-tuple notation:

Q5.  Convert the given ε-NFA to its equivalent DFA:

Continue reading →

Test Your Knowledge on Regular Expressions

Multiple Choice Questions on RE & CFG 

Q1.  Given the language L = {ab, aa, baa}, which of the following strings are in L*? 
        1) abaabaaabaa 
        2) aaaabaaaa 
        3) baaaaabaaaab 
        4) baaaaabaa 

Possible Answers:

        (A) 1, 2 and 3 
        (B) 2, 3 and 4 
        (C) 1, 2 and 4 
        (D) 1, 3 and 4 

Q2. What is the Regular Expression (RE) over the alphabet Σ={a,b} for the language that indicate the strings containing "ab" as substrings?

        (A) (a+b)ab(a+b)

        (B) (a+b)*ab(a+b)*

        (C) (ab)*ab(ab)*

        (D) ab(a+b)*

Q3.  Consider the FA shown in the figure given below, where ‘-’ is the start sate and ‘+’ is the ending state.  The language accepted by the FA is

Q4.  Which regular expression best describe the language accepted by the non-deterministic automaton below?

Q5:

Q6: From the following regular expressions over an alphabet {a, b} given below, which can yield all the possible strings over ∑ (a, b)?

Q7. Which of the following options are correct for the given DFA:

(A) 0(10)*

(B) (01)*0

(C) Both (A) and (B)

(D) Neither (A) nor (B)

Q8. 

Q9. Pumping lemma is generally used for proving which of the following:

(A) A given grammar is regular

(B) A given grammar is non-regular

(C) Whether two given regular expression are equivalent or not

(D) Both (A) and (C)

Q10. Sentence that can be generated from the following production grammar is:

Descriptive Questions on Regular Expressions

Q1. Construct an NFA and a DFA for recognizing the language denoted by the regular expression aa* + bb* 

Q2.  Write regular expressions for the following languages over the alphabet {0, 1}:

    a) The set of all strings that begin with 110.

    b) The set of all strings that contain 1011.

    c) The set of strings of 0's and 1's with at most one pair of consecutive 1's.

Q3.  Write regular expressions for the following languages over the alphabet {a, b}:

    a) The set of strings containing at least one a and at least one b .

Q4.  Convert the following regular expressions to NFA's with ε -transitions.

Continue reading →

Test Your Knowledge on Finite Automata

Multiple Choice Questions on Automata 

Q1. Finite state machine can recognize which of the following languges:

       (A) Only context-free grammar

       (B) Only regular grammar

       (C) Any unambiguous grammar

       (D) Any grammar

Q2. The language, L is defined over Σ = {0, 1, 2, 3, 4, 5, 6, 7} has the following set of strings included in its dictionary:

L = {7, 16, 43, 61, 223, ...} 

Identify the language represented by L from the following options:

       (A) Alternate odd and even numbers

       (B) Octal representation of a number

       (C) Divisible by 7

       (D) Octal representation of a number divisible by 7.

Q3.  Which of the following statements about ε-moves (epsilon transitions) in Finite Automata is correct?

       (A) An ε-move consumes one input symbol from the alphabet

       (B) ε-moves are allowed only in DFA

       (C) ε-moves allow the automaton to change states without consuming any input symbol

       (D) An automaton with ε-move always accepts all input strings

Q4.

       (A) Regular Language

       (B) Context-Sensitive Language

       (C) Context-Free Language

       (D) Phrase-Structure Language

Q5. Consider the given finite automaton and identify the Language recognised by it:

        (A) A DFA that accepts all strings that end with "ba"

        (B) A DFA that accepts all strings that end with "a"

        (C) A DFA that accepts all strings that end with "b"

        (D) A DFA that accepts all strings that end with "ab"

Q6.  In the automaton below, s is the start state and t is only final state.

Q7.  The below transition diagram of a finite automaton accepts which of the following set of strings?

Q8.  For the given NFA which of the following is the equivalent DFA:

Q9. How many states will the DFA equivalent of NFA with n states have in the worst case?

 

        (A) n

        (B) 2n

        (C) 2ⁿ

        (D) n²

Q10. Two finite state machines are said to be equivalent if they:

 

        (A) Have the same number of edges

        (B) Have the same number of states

        (C) Recognise the same set of tokens

        (D) Have the same number of edges and states

Q11.  ‘Every NFA can be simulated by a DFA’. The statement is true/false?

Design Automata for Representing a Language

Q1.  Consider the following NFA and answer the following:

        a) Give all the strings of length three or less accepted by the automaton.

        b) Convert the automaton to a DFA.

Q2.  Consider the following ε-NFA and do the following:

      a) Compute the ε-closure of each state.

        b) Give all the strings of length three or less accepted by the automaton.

        c) Convert the automaton to a DFA.

Q3.  Constructure the Finite Automata from the following 5-tuple notation:

Continue reading →

Automata Theory and Compiler Design (2412PC02)

R24 Syllabus of Automata & Compiler Design

UNIT - I

Introduction to Finite Automata: Structural Representations, Automata and Complexity, the Central Concepts of Automata Theory – Alphabets, Strings, Languages, Problems.

Nondeterministic Finite Automata: Formal Definition, an application, Text Search, Finite Automata with Epsilon-Transitions.

Deterministic Finite Automata: Definition of DFA, How A DFA Process Strings, The language of DFA, Conversion of NFA with €-transitions to NFA without €-transitions, Conversion of NFA to DFA

UNIT - II

Regular Expressions: Finite Automata and Regular Expressions, Applications of Regular Expressions, Algebraic Laws for Regular Expressions, Conversion of Finite Automata to Regular Expressions.

Pumping Lemma for Regular Languages: Statement of the pumping lemma, Applications of the Pumping Lemma.

Context-Free Grammars: Definition of Context-Free Grammars, Derivations Using a Grammar, Leftmost and Rightmost Derivations, the Language of a Grammar, Parse Trees, Ambiguity in Grammars and Languages.

UNIT - III

Push Down Automata: Definition of the Pushdown Automaton, the Languages of a PDA, Equivalence of PDA and CFG’s, Acceptance by final state

Turing Machines: Introduction to Turing Machine, Formal Description, Instantaneous description, The language of a Turing machine

Undecidability: Undecidability, A Language that is Not Recursively Enumerable, An Undecidable Problem That is RE, Undecidable Problems about Turing Machines

UNIT - IV

Introduction: The structure of a compiler,

Lexical Analysis: The Role of the Lexical Analyzer, Input Buffering, Recognition of Tokens, The Lexical- Analyzer Generator Lex,

Syntax Analysis: Introduction, Context-Free Grammars, Writing a Grammar, Top-Down Parsing, Bottom- Up Parsing, Introduction to LR Parsing: Simple LR, More Powerful LR Parsers

UNIT - V

Syntax-Directed Translation: Syntax-Directed Definitions, Evaluation Orders for SDD's, Syntax- Directed Translation Schemes, Implementing L-Attributed SDD's.

Intermediate-Code Generation: Variants of Syntax Trees, Three-Address Code

Run-Time Environments: Stack Allocation of Space, Access to Nonlocal Data on the Stack, Heap Management

Continue reading →