Automata & Its Types (Unit-1)
Multiple Choice Questions (MCQ)
1) Finite state machine can recognize which of the following languages:
(A) Only context-free grammar
(B) Only regular grammar
(C) Any unambiguous grammar
(D) Any grammar
2) 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
3)
(A) Regular Language
(B) Context-Sensitive Language
(C) Context-Free Language
(D) Phrase-Structure Language
4) 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.
5) Consider the given finite automaton and identify the Language recognized 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"
6) In the automaton below, s is the start state and t is only final state.
.png)
7) The below transition diagram of a finite automaton accepts which of the following set of strings?
8) For the given NFA which of the following is the equivalent DFA:
9) ‘Every NFA can be simulated by a DFA’. The statement is true/false?
10) How many states will the DFA equivalent of NFA with n states have in the worst case?
(A) n
(B) 2n
(C) 2n
(D) n2
11) 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
12) 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
Descriptive Questions
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. Construct an NFA and a DFA for recognizing the language denoted by the regular expression aa* + bb*
Q3. 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.
Q4. 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}
Q5. Draw the transition diagram for an NFA which accepts all strings with two consecutive 0’s
Q6. Constructure the Finite Automata from the following 5-tuple notation:
Q7. Construct NFA over the alphabet Σ={a,b} for the language having a set of strings formed using either 101 or 110 as substring.
Q8) Draw the ε-NFA and compute the ε-closure of each state for the given NFA. Also identify the subsets of starting state in DFA.
Solution:
Q9) Constructure the Finite Automata using 5-tuple notation for the recognizing a set of strings that can have 1 followed immediately by 00
