Multiple choice question for engineering
Set 1
1. The class of recursively ennumerable language is known as:
a) Turing Class
b) Recursive Languages
c) Universal Languages
d) RE
Answer
Answer: d [Reason:] RE or recursively ennumerable is only called the class of recursively ennumerable language.
2. A language L is said to be Turing decidable if:
a) recursive
b) TM recognizes L
c) TM accepts L
d) None of the mentioned
Answer
Answer: a,b [Reason:] A language L is recursively ennumerable if there is a turing machine that accepts L, and recursive if there is a TM that recognizes L.(Sometimes these languages are alse called Turing-acceptable and Turing-decidable respectively).
3. Which of the following statements are false?
a) Every recursive language is recursively ennumerable
b) Recursively ennumerable language may not be recursive
c) Recursive languages may not be recursively ennumerable
d) None of the mentioned
Answer
Answer: c [Reason:] Every recursive language is recursively ennumerable but there exists recursively ennumerable languages that are not recursive. If L is accepted by a Non deterministic TM T, and every possible sequence of moves of T causes it to halt, then L is recursive.
4. Choose the correct option:
Statement: If L1 and L2 are recursively ennumerable languages over S, then the following is/are recursively ennumerable.
a) L1 U L2
b) L2 ∩ L2
c) Both (a) and (b)
d) None of the mentioned
Answer
Answer: c [Reason:] Both the union and intersection operations preserve the property of recursive ennumerablity(Theorem).
5. If L is a recursive language, L’ is:
a) Recursive
b) Recursively Ennumerable
c) Both (a) and (b)
d) None of the mentioned
Answer
Answer: c [Reason:] If T is a turing machine recognizing L, we can make it recognize L’ by interchanging the two outputs. And every recursive language is recursively ennumerable.
6. Choose the appropriate option:
Statement: If a language L is recursive, it is closed under the following operations:
a) Union
b) Intersection
c) Complement
d) All of the mentioned
Answer
Answer: d [Reason:] The closure property of recursive languages include union, intersection and complement operations.
7. A recursively ennumerable language L can be recursive if:
a) L’ is recursively ennumerable
b) Every possible sequence of moves of T, the TM which accept L, causes it to halt
c) Both (a) and (b)
d) None of the mentioned
Answer
Answer: c [Reason:] Theorem- If L is a recursively ennumerable language whose complement is recursively ennumerable, then L is recursive.
8. A language L is recursively ennumerable if L=L(M) for some turing machine M.
Which among the following cannot be among A, B and C?
a) yes w ∈ L
b) no w ∉ L
c) M does not halt w ∉ L
d) None of the mentioned
Answer
Answer: d [Reason:]
9. State true or false:
Statement: An ennumerator is a turing machine mwith extra output tape T, where symbols, once written, are never changed.
a) true
b) false
Answer
Answer: a [Reason:] To ennumerate a set means to list the elements once at a time, and to say that a set is ennumerable should perhaps mean that there exists an algorithm for ennumerating it.
10. A Language L may not be accepted by a Turing Machine if:
a) It it is recursively ennumerable
b) It is recursive
c) L can be ennumerated by some turing machine
d) None of the mentioned
Answer
Answer: b [Reason:] A language L is recursively ennumerable if and only if it can be ennumerated by some turing machine. A recursive ennumerable language may or may not be recursive.
Set 2
1. The instantaneous PDA is has the following elements
a) State
b) Unconsumed input
c) Stack content
d) All of the mentioned
Answer
Answer: d [Reason:] The instantaneous description of a PDA is represented by 3 tuple:
(q,w,s)
where q is the state, w is the unconsumed input and s is the stack content.
2. The moves in the PDA is technically termed as:
a) Turnstile
b) Shifter
c) Router
d) None of the mentioned
Answer
Answer: a [Reason:] A turnstile notation is used for connecting pairs od ID’s taht represents one or many moves of a PDA.
3. Which of the following option resembles the given PDA?
a) {0n1n|n>=0}
b) {0n12n|n>=0}
c) {02n1n|n>=0}
d) None of the mentioned
Answer
Answer: a
4. Which of the following correctly resembles the given state diagram?
a) {wwr|w=(a+b)*}
b) ε is called the initial stack symbol
c) Both (a) and (b)
d) None of the mentioned
Answer
Answer: a [Reason:] Initially we put a special symbol ‘#’ into the empty stack. At state q1, the w is being read. In state q2, each 0 or 1 is popped when it matches the input. If any other input is given, the PDA will go to a dead state. When we reach that special symbol ‘#’, we go to the accepting state q3.
5. Which of the following assertion is false?
a) If L is a language accepted by PDA1 by final state, there exist a PDA2 that accepts L by empty stack i.e. L=L(PDA1)=L(PDA2)
b) If L is a CFL then there exists a push down automata P accepting CF; ; by empty stack i.e. L=M(P)
c) Let L is a language accepted by PDA1 then there exist a CFG X such that L(X)=M(P)
d) All of the mentioned
Answer
Answer: d [Reason:]
All the assertions mentioned are theorems or corollary.
6. A push down automata can represented using:
a) Transition graph
b) Transition table
c) ID
d) All of the mentioned
Answer
Answer: d [Reason:] Yes, a PDA can be represented using a transition diagram, transition table and an instantaneous description.
7. State true or false:
Statement: Every context free grammar can be transformed into an equvalent non deterministic push down automata.
a) true
b) false
Answer
Answer: a [Reason:] Push down automata is the automaton machine for all the context free grammar or Type 2 languages.
8. Which of the following statement is false?
a) For non deterministic PDA, equivalence is undecidable
b) For deterministic PDA, equivalence is decidable
c) For deterministic PDA, equivalence is undecidable.
d) None of the mentioned
Answer
Answer: c [Reason:] Geraud proved the equivalence problem decidable for Deterministic PDA .
9. Which of the following are the actions that operates on stack top?
a) Pushing
b) Popping
c) Replacing
d) All of the mentioned
Answer
Answer: d [Reason:] Push, pop and replace are all the basic and only operations that takes place on stack top.
10. A push down automata is said to be _________ if it has atmost one transition around all configurations.
a) Finite
b) Non regular
c) Non-deterministic
d) Deterministic
Answer
Answer: d [Reason:] DPDA or Deterministic Push down automata has atmost one transition applicable to each configuration.
Set 3
1. Which of the following is not a negative property of Context free languages?
a) Intersection
b) Complement
c) Both (a) and (b)
d) None of the mentioned
Answer
Answer: c [Reason:] Context free languages are not closed under complement and intersection. Thus, are called Negative properties.
2. The intersection of context free language and regular language is _________
a) regular language
b) context free language
c) context sensitive language
d) non of the mentioned
Answer
Answer: b [Reason:] If a language L1 is regular and L2 is a context free language, then L1 intersection L2 will result into a context free language.
3. Which of the following is regular?
a) a100b100
b) (a+b)*-{a100b100}
c) Both (a) and (b)
d) None of the mentioned
Answer
Answer: c [Reason:] As the language seems to be finite, a dfa can be constructed for the same, thus is regular.
4. Which of the following is not context free?
a) {w: nA=nB=nC}
b) {a*b*c*}
c) {a100b100}
d) All of the mentioned
Answer
Answer: d [Reason:] {a*b*c*} and (c) are regular languages while option (a) is not context free language.
5. Which of the following can be used to prove a language is not context free?
a) Ardens theorem
b) Power Construction method
c) Regular Closure
d) None of the mentioned
Answer
Answer: c [Reason:] We can use the properties of regular closure to prove that a language is not a context free language. Example: Intersection of context free language and regular language is a context free language. Proof by contradiction helps here.
6. Which of the following are valid membership algorithms?
a) CYK algorithm
b) Exhaustive search parser
c) Both (a) and (b)
d) None of the mentioned
Answer
Answer: c [Reason:] CYK algorithm is a parsing algorithm for context free grammars, which employs bottom up parsing and dynamic programming.
7. Which of the following belong to the steps to prove emptiness?
a) Remove useless variable
b) Check if a start variable S is useless
c) Both (a) and (b)
d) None of the mentioned
Answer
Answer: c [Reason:] The empty-language question can be stated as: For context free grammar G find if L(G) =f?
8. Which of the following is true for CYK Algorithm?
a) Triangular Table
b) Circular Chart
c) Linked List
d) None of the mentioned
Answer
Answer: a [Reason:] A triangular table is constructed to facilitate the solution of membership problem using bottom up parsing and dynamic programming.
9. Which of the following steps are wrong with respect to infiniteness problem?
a) Remove useless variables
b) Remove unit and epsilon production
c) Create dependency graph for variables
d) If there is a loop in the dependency graph the the language is finite else infinite
Answer
Answer: d [Reason:] If we are able to detect a loop in the formed dependency graph, then the language in infinite.
10. State true or false:
Statement: Every context free language can be generated by a grammar which contains no useless non terminals.
a) true
b) false
Answer
Answer: a [Reason:] At first, we detect useless symbols and discard them. Inorder to find whether a symbol is useless, just make it the starting symbol and check for emptiness.
Set 4
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
Answer: b [Reason:] 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
Answer: c [Reason:] 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
Answer: a [Reason:] 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
Answer: b [Reason:] 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
Answer: b [Reason:] 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
Answer: c [Reason:] 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
Answer: d [Reason:] 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
Answer: d [Reason:] 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
Answer: d [Reason:] 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
Answer: a [Reason:] 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
Answer: d [Reason:] 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
Answer: d [Reason:] 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
Answer: d [Reason:] 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
Answer: a [Reason:] 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
Answer: a [Reason:] 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
Answer: c [Reason:] Type checking is a process which is performed during Syntax directed translation.
Set 5
1. XML is a _________ markup language.
a) meta
b) beta
c) octa
d) peta
Answer
Answer: a [Reason:] 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
Answer: b [Reason:] 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
Answer: d [Reason:] 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
Answer: d [Reason:] 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) <!DOCTYPE>
c) Macros
d) None of the mentioned
Answer
Answer: b [Reason:] 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
Answer: d [Reason:] 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
Answer: b [Reason:] 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
Answer: a [Reason:] 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
Answer: d [Reason:] 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: <section>
b) End tags: </section>
c) <img src= “abc.jpeg” >ABC</img>
d) None of the mentioned
Answer
Answer: d [Reason:] All the mentioned options are valid HTML5 arguments and executes properly.
Total Views: 17
