Category: Automata Theory Objective Questions

Automata Theory Multiple Choice Questions on “Equivalence of NFA and DFA”.

1. Under which of the following operation, NFA is not closed?
a) Negation
b) Kleene
c) Concatenation
d) None of the mentioned

Answer: d
Clarification: NFA is said to be closed under the following operations:
a) Union
b) Intersection
c) Concatenation
d) Kleene
e) Negation

2. It is less complex to prove the closure properties over regular languages using
a) NFA
b) DFA
c) PDA
d) Can’t be said

Answer: a
Clarification: We use the construction method to prove the validity of closure properties of regular languages. Thus, it can be observe, how tedious and complex is the construction of a DFA as compared to an NFA with respect to space.

3. Which of the following is an application of Finite Automaton?
a) Compiler Design
b) Grammar Parsers
c) Text Search
d) All of the mentioned

Answer: d
Clarification: There are many applications of finite automata, mainly in the field of Compiler Design and Parsers and Search Engines.

4. John is asked to make an automaton which accepts a given string for all the occurrence of ‘1001’ in it. How many number of transitions would John use such that, the string processing application works?
a) 9
b) 11
c) 12
d) 15
Answer: a

5. Which of the following do we use to form an NFA from a regular expression?
a) Subset Construction Method
b) Power Set Construction Method
c) Thompson Construction Method
d) Scott Construction Method

Answer: c
Clarification: Thompson Construction method is used to turn a regular expression in an NFA by fragmenting the given regular expression through the operations performed on the input alphabets.

6. Which among the following can be an example of application of finite state machine(FSM)?
a) Communication Link
b) Adder
c) Stack
d) None of the mentioned

Answer: a
Clarification: Idle is the state when data in form of packets is send and returns if NAK is received else waits for the NAK to be received.

7. Which among the following is not an application of FSM?
a) Lexical Analyser
b) BOT
c) State charts
d) None of the mentioned

Answer: d
Clarification: Finite state automation is used in Lexical Analyser, Computer BOT (used in games), State charts, etc.

8. L1= {w | w does not contain the string tr }
L2= {w | w does contain the string tr}
Given ∑= {t, r}, The difference of the minimum number of states required to form L1 and L2?
a) 0
b) 1
c) 2
d) Cannot be said
Answer: a

9. Predict the number of transitions required to automate the following language using only 3 states:
L= {w | w ends with 00}
a) 3
b) 2
c) 4
d) Cannot be said
Answer: a

10. The total number of states to build the given language using DFA:
L= {w | w has exactly 2 a’s and at least 2 b’s}
a) 10
b) 11
c) 12
d) 13

Answer: a
Clarification: We need to make the number of a as fixed i.e. 2 and b can be 2 or more. Thus, using this condition a finite automata can be created using 1 states.

Automata Theory Multiple Choice Questions on “Lexical Analysis”.

1. Lexemes can be referred to as:
a) elements of lexicography
b) sequence of alphanumeric characters in a token
c) lexical errors
d) none of the mentioned

Answer: b
Clarification: A lexeme is a string of characters that form a syntactic unit. It is reasonable to say that is the sequence of alphanumeric characters in a token.

2. If the lexical analyser finds a lexeme with the same name as that of a reserved word,it _________
a) overwrites the word
b) overwrites the functionality
c) generates an error
d) something else

Answer: c
Clarification: Reserved words are known as keywords and they are specific and reserved with its functionality to a language. Thus, getting an input with the same name by the analyzer will generate an error.

3. The methodology to show an error when the analyzer faces a keyword over an user’s input is based on:
a) rule priority
b) longest match rule
c) keyword-out rule
d) none of mentioned

Answer: a
Clarification: The lexical analyzer follows the rule priority where its prioritizes keywords over an input it gets with the same name as that of the keyword and thus generates an error.

4. State true or false:
Statement: A lexical analyzer reads the source code line by line.
a) True
b) False

Answer: b
Clarification: A lexical analyzer reads the source code letter by letter and when it encounters a space or an operator or any special character, it decides that the word is completed.

5.Which among the following statement is correct?
Statement 1: When the analyzer scans ‘int’ and ‘intvalue’, it is not able to decide whether the int leads to a keyword or an identifier.
Statement 2: Longest Match Rule

a) Statement 1 is assertion, Statement 2 is the reason
b) Statement 1 is assertion, Statement 2 is the solution
c) There is no such Statement 2
d) This is not a function of Lexical Analyzer

Answer: b
Clarification: The Longest Match rule states that the lexeme scanned should be determined on the basis of longest match among all the token available.

6. The output of the lexical and syntax analyzer can stated as:
a) parse stream, parse tree
b) token tree, parse tree
c) token stream, parse tree
d) all of the mentioned

Answer: c
Clarification: The lexical analyzer outputs the stream of token which is taken up by syntax analyzer one by one against the production rule and parse tree is generated.

7. Which among the following is not a tool to construct lexical analyzer from a regular expression?
a) lex
b) flex
c) jflex
d) none of the mentioned

Answer: d
Clarification: Lexical analysis is done using few tools such as lex, flex and jflex. Jflex is a computer program that generates lexical analyzers (also known as lexers or scanners) and works apparently like lex and flex. Lex is commonly used with yacc parser generator.

8. A program that performs lexical analysis is termed as:
a) scanner
b) lexer
c) tokenizer
d) all of the mentioned

Answer: d
Clarification: A program which performs lexical analysis is called lexer, scanner or lexer. Nowadays, lexer is combined with a parser which allows syntactic analysis.

9. Lexers and parsers are not found in which of the following?
a) compiler front end processing
b) prettyprinters
c) linters
d) none of the mentioned

Answer: d
Clarification: Lexers and parsers are most commonly used in compilers, but it has more application elsewhere like in prettyprinters or linters(application of stylistic formatting conventions to textfiles, source code, etc.).

10. Which phase of compiler includes Lexical Analysis?
a) 1
b) 2
c) 3
d) Its primary function, not in any phase

Answer: a
Clarification: The first phase of compilation process is called lexical analysis. It fragments the source code into token which is the smallest programming unit of a program.

11. Which of the following characters are ignored while lexical analysis?
a) .
b) =
c) #
d) WhiteSpace

Answer: d
Clarification: The lexical analyzer ignores all the whitespaces and fragments the program into tokens.

12. ____________ is used for grouping up of characters into token.
a) Lexical Analyzer
b) oolex
c) jflex
d) All of the mentioned

Answer: d
Clarification: oolex, flex, lex, jflex, all are lexical analyzer tools which perform the following function.

13. The action of parsing the source code into proper syntactic classes is known as:
a) Parsing
b) Interpretation analysis
c) Lexicography
d) Lexical Analysis

Answer: d
Clarification: Lexical analysis or scanning is the process of parsing the source code into proper syntactic classes. It gets things ready for the parser with lexemes to built the parse tree.

14. Which of the following is the task of lexical analysis?
a) To build the uniform symbol table
b) To initialize the variables
c) To organize the variables in a lexical order
d) None of the mentioned

Answer: a
Clarification: Lexical analysis involves the following task:
a) Building a uniform symbol table
b) Parsing the source code into tokens
c) Building a literal and identifier table

15. The scanner outputs:
a) Stream of tokens
b) Image file
c) Intermediate code
d) Machine code

Answer: a
Clarification: A scanner or a lexical analyzer takes a source code as input and outputs a stream of token after fragmenting the code.

16. The phase of compilation which involves type checking is:
a) Parsing
b) Scanning
c) Syntax directed translation
d) Semantic Analyzer

Answer: c
Clarification: Type checking is a process which is performed during Syntax directed translation.

Automata Theory Multiple Choice Questions on “Markup Languages”.

1. XML is a _________ markup language.
a) meta
b) beta
c) octa
d) peta

Answer: a
Clarification: Generally speaking, a meta language is a language used to describe a language. XML is a metalanguage that is used to describe a markup language.

2. XML uses _________ principle to formally describe the data.
a) DDL
b) DTD
c) DML
d) None of the mentioned

Answer: b
Clarification: A document type definition (DTD) is a set of markup declarations that define a document type for an SGML-family markup language (SGML, XML, HTML). A Document Type Definition (DTD) defines the legal building blocks of an XML document. It defines the document structure with a list of legal elements and attributes.

3. Which among the following are true for an Extensible markup language?
a) Human Readable/ Machine Readable
b) Extended from SGML
c) Developed by www consortium
d) All of the mentioned

Answer: d
Clarification: XML is an open format markup language with a filename extension of .xml.

4. Which of them have XML as their default format?
a) IWork
b) LibreOffice
c) OpenOffice
d) All of the mentioned

Answer: d
Clarification: More that hundred of document formats using XML syntax have been developed, including RSS, Atom, SOAP and XHTML.

5. A DTD is associated with a XML file by means of ___________
a) Function
b)
c) Macros
d) None of the mentioned

Answer: b
Clarification: A document type definition defines the legal building blocks of an XML document .

6. Which of the following is not an example of electronic mark up?
a) HTML
b) LaTeX
c) PostScript
d) None of the mentioned

Answer: d
Clarification: There are three categories of electronic markup: presentational, procedural, and descriptive markup. Examples are XML, HTML, LaTeX, etc.

7. troff and nroff are _________ in Unix.
a) functions
b) typesetting tools
c) System sofwares
d) None of the mentioned

Answer: b
Clarification: Early examples of computer markup languages can be found in typesetting tools like troff and nroff in Unix.

8. SGML stands for:
a) Standard Generalized Markup Language
b) Standardized General Markup Language
c) Standard General Markup Language
d) Standard Generalized Markdown Language

Answer: a
Clarification: SGML is an acronym for Standard Generalized Markup Language.

9. Markup Languages are not used for which of the following?
a) playlists
b) content syndication
c) user interfaces
d) none of the mentioned

Answer: d
Clarification: Markup languages originated with text documents, but there is an increasing use of mark up language in presentation of other types of information, including playlists, vector graphics, user interfaces and web services.

10. Which of the following is incorrect for HTML5 markup construct?
a) Start tags:

b) End tags:

c) ABC
d) None of the mentioned

Answer: d
Clarification: All the mentioned options are valid HTML5 arguments and executes properly.

Automata Theory Multiple Choice Questions on “CFL- Other Normal Forms”.

1. The following format of grammatical notation is accepted by which of the following:
AB->CD
A->BC or
A->B or
A->a
where A, B, C, D are non terminal symbols and a is a terminal symbol.
a) Greibach Normal Form
b) Chomsky Nrmal Form
c) Kuroda Normal Form
d) None of the mentioned

Answer: c
Clarification: Linearly Bounded grammar or Kuroda Normal Form allows the following format of grammatical analysis:
AB->CD
A->BC or
A->B or
A->a

2. Every Kuroda Normal form grammar generates ___________
a) Context free grammar
b) Context sensitive grammar
c) Unrestricted grammar
d) None of the mentioned

Answer: b
Clarification: Every context sensitive grammar which does not produce an empty string can be generated by a grammar in Kuroda Normal form.

3. Which of the following can generate Unrestricted grammars?
a) Pentonnen Normal form
b) Floyd Normal form
c) Greibach Normal form
d) None of the mentioned

Answer: a
Clarification: Pentonnen Normal form(for Unrestricted grammars) is a special case where there is a slight modification in the format of Kuroda Normal form.
AB->AD
A->BC
A->a

4. Given a grammar in GNF and a derivable string in the grammar with the length n, any ___________will halt at depth n.
a) top-down parser
b) bottom-up parser
c) multitape turing machine
d) none of the mentioned

Answer: a
Clarification: Given a grammar in GNF and a derivable string in the grammar with the length n, any top-down parser will halt at depth n. As the parameter ‘depth’ is mentioned, we will use a top-down parser. Example-LL parser.

5. Which of the following grammars is similar to Floyd Normal form?
a) Backus Naur Form
b) Kuroda Normal Form
c) Greibach Normal Form
d) Chomsky Normal Form

Answer: a
Clarification: Donald Knuth implied a BNF” syntax in which all definitions have such a form may be said to be in ”Floyd Normal Form”.
A->B|C
A->BC
A->a

6. Which among the following can parse a context free grammar?
a) top down parser
b) bottom up parser
c) CYK algorithm
d) all of the mentioned

Answer: d
Clarification: We use certain algorithms to parse a context free grammar which include the most popular CYK algorithm which employs the concept of bottom up parsing and dynamic parsing.

7. The standard version of CYK algorithm operates only on context free grammars in the following form:
a) Greibach Normal form
b) Chomsky Normal form
c) Backus Naur form
d) All of the mentioned

Answer: b
Clarification: It requires the presence of a context free grammar into Chomsky Normal form to operate. However, every context free grammar can be converted into CNF for keeping the sense of grammar equivalent.

8. The __________ running time of CYK is O(n³ .|G|)
where n is the length of the parse string and |G| is the size of the context free grammar G.
a) worst
b) best
c) average
d) none of the mentioned

Answer: a
Clarification: This is the worst case running time of CYK and and this makes it one of the most efficient algorithms for recognizing general context free languages in practice.

9. Which of the following is true for Valiants algorithm?
a) an extension of CYK
b) deals with efficient multiplication algorithms
c) matrices with 0-1 entries
d) all of the mentioned

Answer: d
Clarification: Valiants algorithm is actually an extention of CYK which even computes the same parsing table yet he showed another method can be utilized fro performing this operation.

10. Which among the following is a correct option in format for representing symbol and expression in Backus normal form?
a) ->expression
b) ::=_expression_
c) =
d) all of the mentioned

Answer: b
Clarification: ::=_expression_ is the correct representation where is a non terminal, and expression consist of one or more sequence of symbols, more sequence are separated by |, indicating a choice.

Automata Theory Multiple Choice Questions on “Non Deterministic Polynomial Time”.

1. What does NP stands for in complexity classes theory?
a) Non polynomial
b) Non-deterministic polynomial
c) Both (a) and (b)
d) None of the mentioned

Answer: b
Clarification: NP is said to be one of the most fundamental complexity classes. NP is an acronym for Non deterministic polynomial time.

2. The hardest of NP problems can be:
a) NP-complete
b) NP-hard
c) P
d) None of the mentioned

Answer: a
Clarification: NP class contains many important problems, the hardest of which is NP-complete, whose solution is sufficient to deal with any other NP problem in polynomial time.

3. Which of the following contains NP?
a) PSPACE
b) EXPSPACE
c) Both (a) and (b)
d) None of the mentioned

Answer: c
Clarification: It is sufficient to construct a PSPACE machine that loops over all proof strings and feeds each one to a polynomial time verifier. It is also contained in EXPTIME, since the same algorithm operates in exponential time.

4. Travelling sales man problem belongs to which of the class?
a) P
b) NP
c) Linear
d) None of the mentioned

Answer: b
Clarification: Travelling Salesman Problem: Given an input matrix of distances between n cities, this problem is to determine if there is a route visiting all cities with total distance less than k.

5. State true or false?
Statement: If a problem X is in NP and a polynomial time algorithm for X could also be used to solve problem Y in polynomial time, then Y is also in NP.
a) true
b) false

Answer: a
Clarification: This is just a commutative property of NP complexity class where a problem is said to be in NP if it can be solved using an algorithm which was used to solve another NP problem in polynomial amount of time.

6. A problem which is both _______ and _________ is said to be NP complete.
a) NP, P
b) NP, NP hard
c) P, P complete
d) None of the mentioned

Answer: a
Clarification: A problem is said to be NP Hard if an algorithm for solving the problem can be translated from for solving any other problem. It is easier to show a problem NP than showing it Np Hard.

7. Which of the following is incorrect for the given phrase
Phrase :’solvable by non deterministic algorithms in polynomial time’
a) NP Problems
b) During control flow, non deterministic algorithm may have more than one choice
c) If the choices that non deterministic algorithm makes are correct, the amount of time it takes is bounded by polynomial time.
d) None of the mentioned

Answer: d
Clarification: Primality testing is a simple example. To decide whether a number is prime or not, one simply selects non deterministically a number checks whether factors exist for the number or not.

8. In terms of NTIME, NP problems are the set of decision problems which can be solved using a non deterministic machine in _______ time.
a) O(n)
b) O(n^1/2)
c) O(n^k), k∈N
d) None of the mentioned

Answer: c
Clarification: The complexity class NP can be defined in terms of NTIME as:
NP=O(n^k) for k ∈N.

9. Which of the following can be used to define NP complexity class?
a) Verifier
b) Polynomial time
c) Both (a) and (b)
d) None of the mentioned

Answer: c
Clarification: NP can be defined using deterministic turing machines as verifiers.

10. Which of the following are not in NP?
a) All problems in P
b) Boolean Satisfiability problems
c) Integer factorization problem
d) None of the mentioned

Answer: d
Clarification: This is a list of some problems which are in NP:
a) All problems in P
b) Decision version of Integer factorization method
c) Graph Isomorphism Problem
d) All NP complete problems, etc.

11. Which of the following does not belong to the closure properties of NP class?
a) Union
b) Concatenation
c) Reversal
d) Complement

Answer: d
Clarification: It is unknown about the closure property-complement for the complexity class NP. The question is so called NP versus co-NP problem.

Automata Theory Multiple Choice Questions on “Applications of DFA”.

1. Given Language: {x | it is divisible by 3}
The total number of final states to be assumed in order to pass the number constituting {0, 1} is
a) 0
b) 1
c) 2
d) 3
Answer: c

2. A binary string is divisible by 4 if and only if it ends with:
a) 100
b) 1000
c) 1100
d) 0011

Answer: a
Clarification: If the string is divisible by four, it surely ends with the substring ‘100’ while a binary string divisible by 2 would surely end with the substring ‘10’.

3. Let L be a language whose FA consist of 5 acceptance states and 11 non final states. It further consists of a dumping state. Predict the number of acceptance states in L^c.
a) 16
b) 11
c) 5
d) 6

Answer: a
Clarification: If L leads to FA1, then for L^c, the FA can be obtained by exchanging the final and non-final states.

4. If L1 and L2 are regular languages, which among the following is an exception?
a) L1 U L2
b) L1 – L2
c) L1 ∩ L2
d) All of the mentioned

Answer: d
Clarification: It the closure property of Regular language which lays down the following statement:
If L1, L2 are 2- regular languages, then L1 U L2, L1 ∩ L2, L1^C, L1 – L2 are regular language.

5. Predict the analogous operation for the given language:
A: {[p, q] | p ϵ A1, q does not belong to A2}
a) A1-A2
b) A2-A1
c) A1.A2
d) A1+A2

Answer: a
Clarification: When set operation ‘-‘ is performed between two sets, it points to those values of prior set which belongs to it but not to the latter set analogous to basic subtraction operation.

6. There exists an initial state, 17 transition states, 7 final states and one dumping state, Predict the maximum number of states in its equivalent DFA?
a) 226
b) 224
c) 225
d) 223

Answer: a
Clarification: The maximum number of states an equivalent DFA can comprise for its respective NFA with k states will be 2^k.

7. Statement 1: NFA computes the string along parallel paths.
Statement 2: An input can be accepted at more than one place in an NFA.
Which among the following options are most appropriate?
a) Statement 1 is true while 2 is not
b) Statement 1 is false while is not
c) Statement 1 and 2, both are true
d) Statement 1 and 2, both are false

Answer: c
Clarification: While the machine runs on some input string, if it has the choice to split, it goes in all possible way and each one is different copy of the machine. The machine takes subsequent choice to split further giving rise to more copies of the machine getting each copy run parallel. If any one copy of the machine accepts the strings, then NFA accepts, otherwise it rejects.

8. Which of the following options is correct for the given statement?
Statement: If K is the number of states in NFA, the DFA simulating the same language would have states less than 2^k.
a) True
b) False

Answer: a
Clarification: If K is the number of states in NFA, the DFA simulating the same language would have states equal to or less than 2^k.

9. Let N (Q, ∑, δ, q0, A) be the NFA recognizing a language L. Then for a DFA (Q’, ∑, δ’, q0’, A’), which among the following is true?
a) Q’ = P(Q)
b) Δ’ = δ’ (R, a) = {q ϵ Q | q ϵ δ (r, a), for some r ϵ R}
c) Q’={q0}
d) All of the mentioned

Answer: d
Clarification: All the optioned mentioned are the instruction formats of how to convert a NFA to a DFA.