Category: Automata Theory Objective Questions

Automata Theory Multiple Choice Questions on “CFL- Closure Properties/Decision Properties”.

1. The context free languages are closed under:
a) Intersection
b) Complement
c) Kleene
d) None of the mentioned

Answer: c
Clarification: Context free languages are closed under the following operation: union, kleene and concatenation. For regular languages, we can add intersection and complement to the list.

2. Given Grammar G1:
S->aSb
S->e
Grammar G2:
R->cRd
R->e
If L(G)=L(G1) U L(G2), the number of productions the new starting variable would have:
a) 2
b) 3
c) 4
d) 1

Answer: a
Clarification:
T->S|R
S->aSb
S->e
R->cRd
R->e

3. Context free languages are not closed under:
a) Intersection
b) Intersection with Regular Language
c) Complement
d) All of the mentioned

Answer: d
Clarification: It is a theorem which states that, Context free languages are not closed under operations like intersection and complement.

4. Which of the following is incorrect?
There exists algorithms to decide if:
a) String w is in CFL L
b) CFL L is empty
c) CFL L is infinite
d) All of the mentioned

Answer: d
Clarification: These properties are termed as decision properties of a CFL and include a set of problems like infiniteness problem, emptiness problem and membership problem.

5. If the start symbol is one of those symbols which produce no terminal through any sequence, the CFL is said to be
a) nullable
b) empty
c) eliminated
d) none of the mentioned

Answer: b
Clarification: In the process of removing useless symbols, if the starting symbol is also a part, the CFL can be then termed as empty; otherwise not.

6. Using the pumping constant n, If there is a string in the language of length between _____ and ____ then the language is infite else not.
a) n, 2n-1
b) 2n, n
c) n+1, 3n+6
d) 0, n+1

Answer: a
Clarification: If there is a string in the language of length between n and 2n-1 then the language is infite else not. The idea is essentially the same for regular languages.

7. Which of the following is/are CFL not closed under?
a) Reverse
b) Homomorphism
c) Inverse Homomorphism
d) All of the mentioned

Answer: d
Clarification: CFL is closed under union, kleene and concatenation along with the properties reversal,homomorphism and inverse homomorphism but not difference and intersection.

8. If L1 and L2 are context free languages, L1-L2 are context free:
a) always
b) sometimes
c) never
d) none of the mentioned

Answer: c
Clarification: Context free languages are not closed under difference, intersection and complement operations.

9. A___________ is context free grammar with atmost one non terminal in the right handside of the production.
a) linear grammar
b) linear bounded grammar
c) regular grammar
d) none of the mentioned

Answer: a
Clarification: A simple linear grammar is G with N = {S}, Σ = {a, b}, P with start symbol S and rules
S → aSb
S → ε

10. There is a linear grammar that generates a context free grammar
a) always
b) never
c) sometimes
d) none of the mentioned

Answer: c
Clarification: Linear grammar is a subset of context free grammar which has atmost one non terminal symbol in the right hand side of the production.Thus, there exists some languages which are generated by Linear grammars.

Automata Theory Interview Questions and Answers for Experienced people on “Problem Solvable in Polynomial Time”.

1. If the number of steps required to solve a problem is O(n^k), then the problem is said to be solved in:
a) non-polynomial time
b) polynomial time
c) infinite time
d) none of the mentioned

Answer: b
Clarification: Most of the operations like addition, subtraction, etc as well as computing functions including powers, square roots and logarithms can be performed in polynomial time. In the given question, n is the complexity of the input and k is some non negative integer.

2. The value of constants like p and e can be calculated in:
a) polynomial time
b) non-polynomial time
c) cannot be calculated
d) none of the mentioned

Answer: a
Clarification: The value of such constants can be calculated using algorithms which have time complexity in terms if O(n^k) i.e polynomial time.

3. Which of the following cannot be solved using polynomial time?
a) Linear Programming
b) Greatest common divisor
c) Maximum matching
d) None of the mentioned

Answer: d
Clarification: In graph theory, a matching or independent edge set in a graph G is a set of edges without common vertices. Given a graph (V, E), a matching M in G is a set of pairwise non adjacent edges i.e. no two edges share a common vertex.

4. The complexity class P consist of all the decision problems that can be solved by ___________using polynomial amount of computation time.

a) Push Down automata
b) DFA
c) NDFA
d) Deterministic Turing machine

Answer: d
Clarification: All the decision problems that can be solved using a Deterministic turing machine using polynomial time to compute, all belong to the complexity class P.

5. A generalization of P class can be:
a) PTIME
b) DTIME
c) NP
d) None of the mentioned

Answer: c
Clarification: P is a specific case of NP class, which is the class of decidable problems decidable by a non deterministic turing machine that runs in polynomial time.

6. Which of the following options are correct with reference to P-complete problems?
a) used for the problems which are difficult to solve in limited space
b) every problem in P can be reduced to it using proper reductions
c) complete problem for complexity class P
d) all of the mentioned

Answer: d
Clarification:
The notion of P-complete decision problems is useful in the analysis of:
a) which problems are tough to parallelize effectively
b) which problems are difficult to solve in limited space

7. A problem X belongs to P complexity class if there exist ________ algorithm to solve that problem, such that the number of steps of the algorithms bounded by a polynomial in n, where n is the length of the input.
a) 1
b) 2
c) 3
d) all of the mentioned

Answer: d
Clarification: A problem X belongs to P complexity class if there exist atleast 1 algorithm to solve that problem, such that the number of steps of the algorithms bounded by a polynomial in n, where n is the length of the input. Thus, all the options are correct.

8. Which of the following is a P-complete type of problem?
a) Circuit Value problem
b) Linear programming
c) Context free grammar membership
d) All of the mentioned

Answer: d
Clarification: Given a context free grammar and a string, can the string be generated by the grammar? Such problems fall in the category of P-complete.

9. State true or false?
Statement: Given a turing machine, an input for the machine, and a number T(unary), does that machine halt on that input within the first T-steps?
The given problem is P-complete.
a) true
b) false

Answer: a
Clarification: If we can parallelize a general simulation of a sequential computer, then we will be able to parallelize any program that runs on that computer. If this problem is in NC, then so every other problem in P.

10. In the above problem, if the input is binary, the class the problem belongs?
a) EXPSPACE
b) DLOGTIME
c) EXPTIME-complete
d) All of the mentioned

Answer: c
Clarification: It is the set of all decision problems that have exponential run time i.e. solvable by deterministic turing machine in O(2^p(n)) time, where p(n) is a polynomial function of n.

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.