1. How many strings of length less than 4 contains the language described by the regular expression (x+y)*y(a+ab)*?
a) 7
b) 10
c) 12
d) 11
View Answer
Explanation : string of length 0 = 1
string of length 1 = 4
string of length 2 = 3
string of length 3 = 3
2. Which of the following regular expression is equivalent to R(1,0)?
R(1,0)={111*}*
a) (11+111)*
b) (111+1111)*
c) (111+11*)*
d) All of the mentioned
View Answer
Explanation: What we observe from the question is that, it includes e and 11 and any number of 1’s then. Therefore, its simplifies when we write the same reg. Expression as (11+111)*.
a) Recursive Inference
b) Derivations
c) Both Recursive Inference and Derivations
d) None of the mentioned
View Answer
Explanation: Two inference approaches:
1. Recursive inference, using productions from body to head
2. Derivations, using productions from head to body
DFA,NFA and NFA with epsilon transitions
a) DFA and NFA
b) NFA and epsilon NFA
c) DFA and epsilon NFA
d) All of the mentioned
View Answer
Explanation: For a given automata, all the formats of representation be it deterministic finite automata or non deterministic finite automata or non deterministic finite automata with epsilon transitions, all are equivalent variants.
5. Let the class of language accepted by finite state machine be L1 and the class of languages represented by regular expressions be L2 then
a) L1<L2
b) L1>=L2
c) L1 U L2 = .*
d) L1=L2
View Answer
Explanation : Finite state machine and regular expression have same power to express a language.
6. Which of the following options is incorrect?
a) A language L is regular if and only if ~L has finite number of equivalent classes.
b) Let L be a regular language. If ~L has k equivalent classes, then any DFA that recognizes L must have atmost k states.
c) A language L is NFA-regular if and only if it is DFA-regular.
d) None of the mentioned
View Answer
Explanation: Let L be a regular language. If ~L has k equivalent classes, then any DFA that recognizes L must have atleast k states.
a) Type 0 language
b) Type 1 language
c) Type 2 language
d) Type 3 language
View Answer
Explanation : According to Chomsky hierarchy .
8. What does the following segment of code does?
grep -i man heroes.txt
a) manually opens a file called heroes.txt
b) manages heroes.txt
c) search for “man” in the file “heroes.txt”
d) none of the mentioned
View Answer
Explanation: grep is a command which finds the pattern in a particular text segment.Here, it scans each line in heroes.txt and looks for an m followed by a and then followed by n.
9. Let h(L) be a language of regular expression abe*+e(ab)*. Simplify the h(L)
a) (ab)*+eab*
b) abe*+ea*b*
c) (ab)*
d) None of the mentioned
View Answer
abe*+e(ab)*(Using the identities e=e*, eE=Ee=E)
=ab+(ab)*=> ab will contain inside (ab)*, thus =>(ab)*.
(011+1)*(01)*
a) 4
b) 3
c) 5
d) 6
View Answer
Explanation: The grammar can be written as:
S->BC
B->AB|e
A->011|1
C->DC|e
D->01
Statement: Unambiguity is the ideal structure of a language.
a) true
b) partially true
c) false
d) cant be said
View Answer
Explanation: Ideally, there should be only one parse tree for each string, i.e. the language should be unambiguous.
a) LL parser
b) Recursive descent parser
c) Earley parsers
d) All of the mentioned
View Answer
Explanation: All the following mentioned are top down parsers and begin their operation from the starting symbol.
a) Windows
b) DOS
c) Unix
d) openSUSE
View Answer
Explanation: YACC technique is a computer code for the Unix operating system. It is a LALR parser generator, generating a parser, the part of a compiler that tries to make syntactic sense of the source code.
14. XML uses _________ principle to formally describe the data.
a) DDL
b) DTD
c) DML
d) None of the mentioned
View Answer
Explanation: 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.
a) It has more than one rightmost derivations
b) It has more than one leftmost derivations
c) No parse tree can be generated for the CFG
d) None of the mentioned
View Answer
Explanation: A context free grammar is ambiguous if it has more than one parse tree generated or more than one leftmost derivations. An unambiguous grammar is a context free grammar for which every valid string has a unique leftmost derivation.
