1. The entity which generate Language is termed as:
a) Automata
b) Tokens
c) Grammar
d) Data
Answer: c
Explanation: The entity which accepts a language is termed as Automata while the one which generates it is called Grammar. Tokens are the smallest individual unit of a program.
2. Production Rule: aAb->agb belongs to which of the following category?
a) Regular Language
b) Context free Language
c) Context Sensitive Language
d) Recursively Ennumerable Language
Answer: c
Explanation: Context Sensitive Language or Type 1 or Linearly Bounded Non deterministic Language has the production rule where the production is context dependent i.e. aAb->agb.
4. The Grammar can be defined as: G=(V, ∑, p, S)
In the given definition, what does S represents?
a) Accepting State
b) Starting Variable
c) Sensitive Grammar
d) None of these
Answer: b
Explanation: G=(V, ∑, p, S), here V=Finite set of variables, ∑= set of terminals, p= finite productions, S= Starting Variable.
5. Which among the following cannot be accepted by a regular grammar?
a) L is a set of numbers divisible by 2
b) L is a set of binary complement
c) L is a set of string with odd number of 0
d) L is a set of 0n1n
Answer: d
Explanation: There exists no finite automata to accept the given language i.e. 0n1n. For other options, it is possible to make a dfa or nfa representing the language set.
6. Which of the expression is appropriate?
For production p: a->b where a∈V and b∈_______
a) V
b) S
c) (V+∑)*
d) V+ ∑
Answer: c
Explanation: According to the definition, the starting variable can produce another variable or any terminal or a variable which leads to terminal.
7. For S->0S1|e for ∑={0,1}*, which of the following is wrong for the language produced?
a) Non regular language
b) 0n1n | n>=0
c) 0n1n | n>=1
d) None of the mentioned
Answer: d
Explanation: L={e, 01, 0011, 000111, ……0n1n }. As epsilon is a part of the set, thus all the options are correct implying none of them to be wrong.
8. The minimum number of productions required to produce a language consisting of palindrome strings over ∑={a,b} is
a) 3
b) 7
c) 5
d) 6
Answer: c
Explanation: The grammar which produces a palindrome set can be written as:
S-> aSa | bSb | e | a | b
L={e, a, b, aba, abbbaabbba…..}
9. Which of the following statement is correct?
a) All Regular grammar are context free but not vice versa
b) All context free grammar are regular grammar but not vice versa
c) Regular grammar and context free grammar are the same entity
d) None of the mentioned
Answer: a
Explanation: Regular grammar is a subset of context free grammar and thus all regular grammars are context free.
10. Are ambiguous grammar context free?
a) Yes
b) No
Answer: a
Explanation: A context free grammar G is ambiguous if there is atleast one string in L(G) which has two or more distinct leftmost derivations.
11. Which of the following is not a notion of Context free grammars?
a) Recursive Inference
b) Derivations
c) Sentential forms
d) All of the mentioned
Answer: d
Explanation: The following are the notions to express Context free grammars:
a) Recursive Inferences
b) Derivations
c) Sentential form
d) Parse trees
12. State true or false:
Statement: The recursive inference procedure determines that string w is in the language of the variable A, A being the starting variable.
a) true
b) false
Answer: a
Explanation: We apply the productions of CFG to infer that certain strings are in the language of a certain variable.
13. Which of the following is/are the suitable approaches for inferencing?
a) Recursive Inference
b) Derivations
c) Both Recursive Inference and Derivations
d) None of the mentioned
Answer: c
Explanation: Two inference approaches:
1. Recursive inference, using productions from body to head
2. Derivations, using productions from head to body
14. If w belongs to L(G), for some CFG, then w has a parse tree, which defines the syntactic structure of w. w could be:
a) program
b) SQL-query
c) XML document
d) All of the mentioned
Answer: d
Explanation: Parse trees are an alternative representation to derivations and recursive inferences. There can be several parse trees for the same string.
15. Is the following statement correct?
Statement: Recursive inference and derivation are equivalent.
a) Yes
b) No
Answer: a
Explanation: Yes, they are equivalent. Both the terminologies represent the two approaches of recursive inferencing.
16. A->aA| a| b
The number of steps to form aab:
a) 2
b) 3
c) 4
d) 5
Answer: b
Explanation: A->aA=>aaA=>aab
17. An expression is mentioned as follows. Figure out number of incorrect notations or symbols, such that a change in those could make the expression correct.
L(G)={w in T*|S→*w}
a) 0 Errors
b) 1 Error
c) 2 Error
d) Invalid Expression
Answer: a
Explanation: For the given expression, L(G)={w in T*|S→*w}, If G(V, T, P, S) is a CFG, the language of G, denoted by L(G), is the set of terminal strings that have derivations from the start symbol.
18. The language accepted by Push down Automaton:
a) Recursive Language
b) Context free language
c) Linearly Bounded language
d) All of the mentioned
Answer: b
Explanation: Push down automata accepts context free language.
19. Which among the following is the correct option for the given grammar?
G->X111|G1,X->X0|00
a) {0a1b|a=2,b=3}
b) {0a1b|a=1,b=5}
c) {0a1b|a=b}
d) More than one of the mentioned is correct
Answer: a
Explanation: Using the recursive approach, we can conclude that option a is the correct answer, and its not possible for a grammar to have more than one language.
20. Which of the following the given language belongs to?
L={ambmcm| m>=1}
a) Context free language
b) Regular language
c) Both (a) and (b)
d) None of the mentioned
Answer: d
Explanation: The given language is neither accepted by a finite automata or a push down automata. Thus, it is neither a context free language nor a regular language.
21. Choose the correct option:
Statement: There exists two inference approaches:
a) Recursive Inference
b) Derivation
a) true
b) partially true
c) false
d) none of the mentioned
Answer: a
Explanation: We apply the productions of a CFG to infer that certain strings are in a language of certain variable.
22. Choose the correct option:
Statement 1: Recursive Inference, using productions from head to body.
Statement 2: Derivations, using productions from body to head.
a) Statement 1 is true and Statement 2 is true
b) Statement 1 and Statement 2, both are false
c) Statement 1 is true and Statement 2 is false
d) Statement 2 is true and Statement 1 is true
Answer: b
Explanation: Both the statements are false. Recursive Inference, using productions from body to head. Derivations, using productions from head to body.
23. Which of the following statements are correct for a concept called inherent ambiguity in CFL?
a) Every CFG for L is ambiguous
b) Every CFG for L is unambiguous
c) Every CFG is also regular
d) None of the mentioned
Answer: a
Explanation: A CFL L is said to be inherently ambiguous if every CFG for L is ambiguous.
24. Which of the theorem defines the existence of Parikhs theorem?
a) Parikh’s theorem
b) Jacobi theorem
c) AF+BG theorem
d) None of the mentioned
Answer: a
Explanation: Rohit Parikh in 1961 proved in his MIT research paper that some context free language can only have ambiguous grammars.
25. State true or false:
Statement: Every right-linear grammar generates a regular language.
a) True
b) False
Answer: a
Explanation: A CFG is said to right linear if each production body has at most one variable, and that variable is at the right end. That is, all productions of a right linear grammar are of the form A->wB or A->w, where A and B are variables while w is some terminal.
26. What the does the given CFG defines?
S->aSbS|bSaS|e and w denotes terminal
a) wwr
b) wSw
c) Equal number of a’s and b’s
d) None of the mentioned
Answer: c
Explanation: Using the derivation approach, we can conclude that the given grammar produces a language with a set of string which have equal number of a’s and b’s.
27. If L1 and L2 are context free languages, which of the following is context free?
a) L1*
b) L2UL1
c) L1.L2
d) All of the mentioned
Answer: d
Explanation: The following is a theorem which states the closure property of context free languages which includes Kleene operation, Union operation and Dot operation.
28. For the given Regular expression, the minimum number of variables including starting variable required to derive its grammar is:
(011+1)*(01)*
a) 4
b) 3
c) 5
d) 6
Answer: c
Explanation: The grammar can be written as:
S->BC
B->AB|ε
A->011|1
C->DC|ε
D->01
29. For the given Regular expression, the minimum number of terminals required to derive its grammar is:
(011+1)*(01)*
a) 4
b) 3
c) 5
d) 6
Answer: b
Explanation: The grammar can be written as:
S->BC
B->AB|ε
A->011|1
C->DC|ε
D->01
30. A grammar G=(V, T, P, S) is __________ if every production taken one of the two forms:
B->aC
B->a
a) Ambiguous
b) Regular
c) Non Regular
d) None of the mentioned
Answer: b
Explanation: The following format of grammar is of Regular grammar and is a part of Context free grammar i.e. like a specific form whose finite automata can be generated.
31. Which among the following is a CFG for the given Language:
L={x∈{0,1}*|number of zeroes in x=number of one’s in x}
a) S->e|0S1|1S0|SS
b) S->0B|1A|e A->0S B->1S
c) All of the mentioned
Answer: c
Explanation: We can build context free grammar through different approaches, recursively defining the variables and terminals inorder to fulfil the conditions.
32. Which of the following languages are most suitable for implement context free languages ?
a) C
b) Perl
c) Assembly Language
d) None of the mentioned
View Answer
Answer: a
Explanation: The advantage of using high level programming language like C and Pascal is that they allow us to write statements that look more like English.
33. Which among the following is the correct grammar for the given language?
L={x∈{0,1}*|number of zeroes in x¹number of one’s in x}
a) S-> 0|SS|1SS|SS1|S1S
b) S-> 1|0S|0SS|SS0|S0S
c) S-> 0|0S|1SS|SS1|S1S
d) None of the mentioned
Answer: c
Explanation: L={0, 1, 00, 11, 001, 010,…}
The grammar can be framed as: S-> 0|0S|1SS|SS1|S1S
34. L={0i1j2k | j>i+k}
Which of the following satisfies the language?
a) 0111100
b) 011100
c) 0001100
d) 0101010
Answer: a
Explanation: It is just required to put the value in the variables in the question and check if it satisfies or not.
35. The most suitable data structure used to represent the derivations in compiler:
a) Queue
b) Linked List
c) Tree
d) Hash Tables
Answer: c
Explanation: The tree, known as “Parse tree” when used in a compiler, is the data structure of choice to represent the source program.
36. Which of the following statement is false in context of tree terminology?
a) Root with no children is called a leaf
b) A node can have three children
c) Root has no parent
d) Trees are collection of nodes, with a parent child relationship
Answer: a
Explanation: A node has atmost one parent, drawn above the node, and zero or more children drawn below. Lines connect parents to children. There is one node, one root, that has no parent; this node appears to be at the top of the tree. Nodes with no children are called leaves. Nodes that are not leaves are called interior nodes.
37. In which order are the children of any node ordered?
a) From the left
b) From the right
c) Arbitrarily
d) None of the mentioned
Answer: a
Explanation: The children of a node are ordered from the left and drawn so. If N is to the left of node M, then all the descendents of N are considered to be to the left of all the descendents of M.
38. Which among the following is the root of the parse tree?
a) Production P
b) Terminal T
c) Variable V
d) Starting Variable S
Answer: d
Explanation: The root is labelled by the start symbol. All the leaves are either labelled by a a terminal or with e.
42. A grammar with more than one parse tree is called:
a) Unambiguous
b) Ambiguous
c) Regular
d) None of the mentioned
Answer: b
Explanation: A context free grammar G is ambiguous if there is at least one string in L(G) having two or more distinct derivation trees or equivalently, two or more distinct leftmost derivations.
43. __________ is the acyclic graphical representation of a grammar.
a) Binary tree
b) Oct tree
c) Parse tree
d) None of the mentioned
Answer: c
Explanation: In order to graphically represent a derivation of a grammar we need to use parse trees.
44. Grammar is checked by which component of compiler
a) Scanner
b) Parser
c) Semantic Analyzer
d) None of the mentioned
Answer: Parser or syntax analyzer is the one responsible for checking the grammar and reporting errors. In this phase, parse tree is generated and syntax is analyzed.
45. To derive a string using the production rules of a given grammar, we use:
a) Scanning
b) Parsing
c) Derivation
d) All of the mentioned
Answer: b
Explanation: Parsing is required to check the acceptability of a string. Further, comes the syntactical phase which is taken care by other phases of compiler.
46. Which of the following parser reaches the root symbol of the tree at last?
a) Top down parser
b) Bottom up parser
c) TOP down and Bottom up parser
d) None of the mentioned
Answer: b
Explanation: Bottom up parser starts from the bottom with the string and comes up to the start symbolusing a parse tree or a derivation tree.
47. Left corner parsing methof uses which of the following?
a) Top down parser
b) Bottom up parser
c) TOP down and Bottom up parser
d) None of the mentioned
Answer: c
Explanation: It is a hybrid method which works bottom up along the left edges of each subtree, and top down on the rest of the parse tree.
48. Which of the following parser performs top down parsing?
a) LALR parser
b) LL parser
c) Recursive Accent parser
d) None of the mentioned
Answer: b
Explanation: Bottom up parsing is done by shift reduce parsers like LALR parsers, Operator precedence parsers, simple precedence parsers, etc.
49. Which of the following is true for shift reduce parsers?
a) Scans and parses the input in one forward pass over the text, without any backup.
b) A shift command advances in the input stream by one symbol
c) LALR parser
d) All of the mentioned
Answer: d
Explanation: The mentioned are the correct and proper functions of a shift reduce parsers. The parsing methods are most commonly used for parsing programming languages, etc.
50. State true or false:
Statement: LALR parsers uses tables rather than mutually recursive functions.
a) true
b) false
Answer: b
Explanation: It is exactly the opposite case where LALR parsers uses mutually recursive functions instead of tables. It is a simplified version of canonical left to right parser.
51. LALR in LALR parser stands for:
a) Left aligned left right parser
b) Look ahead left to right parser
c) Language Argument left to right parser
d) None of the mentioned
Answer:
Explanation: LALR stands for Look ahead left to right parsers. It has more language recognition power than LR(0) parser.
52. Which of the following can be a LALR parser generator?
a) YACC
b) GNU Bison
c) YACC and GNU Bison
d) None of the mentioned
Answer: c
Explanation: YACC is a computer code for UNIX operating system which generates a LALR parser. On the other hand GNU Bison or Bison can generate LALR and GLR parsers.
53. Which of the following parsers do not relate to Bottom up parsing?
a) LL parser
b) Recursive descent parser
c) Earley parsers
d) All of the mentioned
Answer: d
Explanation: All the following mentioned are top down parsers and begin their operation from the starting symbol.
54. Which of the following is true for a predictive parser?
a) Recursive Descent parser
b) no backtracking
c) Recursive Descent parser and no backtracking
d) None of the mentioned
Answer: c
Explanation: Predictive parsing is possible only for the class of LL-grammars, which are the CFG for which there exists some positive integer k that allows a recursive descent parser to decide which production to use by examining only the next k tokens of input.
55. The format: A->aB refers to which of the following?
a) Chomsky Normal Form
b) Greibach Normal Form
c) Backus Naur Form
d) None of the mentioned
Answer: b
Explanation: A context free grammar is in Greibach Normal Form if the right hand sides of all the production rules start with a terminal, optionally followed by some variables.
56. Which of the following does not have left recursions?
a) Chomsky Normal Form
b) Greibach Normal Form
c) Backus Naur Form
d) All of the mentioned
Answer: b
Explanation: The normal form is of the format:
A->aB where the right hand side production tends to begin with a terminal symbo, thus having no left recursions.
57. Every grammar in Chomsky Normal Form is:
a) regular
b) context sensitive
c) context free
d) all of the mentioned
Answer: c
Explanation: Conversely, every context frr grammar can be converted into Chomsky Normal form and to other forms.
58. Which of the production rule can be accepted by Chomsky grammar?
a) A->BC
b) A->a
c) S->e
d) All of the mentioned
Answer: d
Explanation: in CNF, the production rules are of the form:
A->BC
A-> a
S->e
59. Given grammar G:
(1)S->AS
(2)S->AAS
(3)A->SA
(4)A->aa
Which of the following productions denies the format of Chomsky Normal Form?
a) 2,4
b) 1,3
c) 1, 2, 3, 4
d) 2, 3, 4
Answer: a
Explanation: The correct format: A->BC, A->a, X->e.
60. Which of the following grammars are in Chomsky Normal Form:
a) S->AB|BC|CD, A->0, B->1, C->2, D->3
b) S->AB, S->BCA|0|1|2|3
c) S->ABa, A->aab, B->Ac
d) All of the mentioned
Answer: a
Explanation: We can eliminate the options on the basis of the format we are aware of: A->BC, B->b and so on.
61. With reference to the process of conversion of a context free grammar to CNF, the number of variables to be introduced for the terminals are:
S->ABa
A->aab
B->Ac
a) 3
b) 4
c) 2
d) 5
Answer: a
Explanation: According to the number of terminals present in the grammar, we need the corresponding that number of terminal variables while conversion.
62. In which of the following, does the CNF conversion find its use?
a) CYK Algorithm
b) Bottom up parsing
c) Preprocessing step in some algorithms
d) All of the mentioned
Answer: d
Explanation: Besides the theoretical significance of CNF, it conversion scheme is helpful in algorithms as a preprocessing step, CYK algorithms and the bottom up parsing of context free grammars.
63. Let G be a grammar. When the production in G satisfy certain restrictions, then G is said to be in ___________.
a) restricted form
b) parsed form
c) normal form
d) all of the mentioned
Answer: c
Explanation: When the production in G satisfy certain restrictions, then G is said to be in ‘normal form’.
64. Let G be a grammar: S->AB|e, A->a, B->b
Is the given grammar in CNF?
a) Yes
b) No
Answer: a
Explanation: e is allowed in CNF only if the starting variable does not occur on the right hand side of the derivation.
65. Which of the following is called Bar-Hillel lemma?
a) Pumping lemma for regular language
b) Pumping lemma for context free languages
c) Pumping lemma for context sensitive languages
d) None of the mentioned
Answer: b
Explanation: In automata theory, the pumping lemma for context free languages, also kmown as the Bar-Hillel lemma, represents a property of all context free languages.
66. Which of the expressions correctly is an requirement of the pumping lemma for the context free languages?
a) uvnwxny
b) uvnwnxny
c) uv2nwx2ny
d) All of the mentioned
Answer: b
Explanation: Let L be a CFL. Then there is an integer n so that for any u that belong to language L satisfying |t| >=n, there are strings u, v, w, x, y and z satisfying
t=uvwxy
|vx|>0
|vwx|<=n For any m>=0, uvnwxny ∈ L
67.Let L be a CFL. Then there is an integer n so that for any u that belong to language L satisfying
|t|>=n, there are strings u, v, w, x, y and z satisfying
t=uvwxy.
Let p be the number of variables in CNF form of the context free grammar. The value of n in terms of p :
a) 2p
b) 2p
c) 2p+1
d) p2
Answer: c
Explanation: This inequation has been derived from derivation tree for t which must have height at least p+2(It has more than 2p leaf nodes, and therefore its height is >p+1).
68. Which of the following gives a positive result to the pumping lemma restrictions and requirements?
a) {aibici|i>=0}
b) {0i1i|i>=0}
c) {ss|s∈{a,b}*}
d) None of the mentioned
Answer: b
Explanation: A positive result to the pumping lemma shows that the language is a CFL and ist contradiction or negative result shows that the given language is not a Context Free language.
69. Using pumping lemma, which of the following cannot be proved as ‘not a CFL’?
a) {aibici|i>=0}
b) {ss|s∈{a,b}*}
c) The set legal C programs
d) None of the mentioned
Answer: d
Explanation: There are few rules in C that are context dependent. For example, declaration of a variable before it can be used.
70. State true or false:
Statement: We cannot use Ogden’s lemma when pumping lemma fails.
a) true
b) false
Answer: b
Explanation: Although the pumping lemma provides some information about v and x that are pumped, it says little about the location of these substrings in the string t. It can be used whenever the pumping lemma fails. Example: {apbqcrds|p=0 or q=r=s}, etc.
71. Which of the following cannot be filled in the blank below?
Statement: There are CFLs L1 nad L2 so that ___________is not a CFL.
a) L1∩L2
b) L1′
c) L1*
d) None of the mentioned
Answer: c
Explanation: A set of context free language is closed under the following operations:
a) Union
b) Concatenation
c) Kleene
72. The pumping lemma is often used to prove that a language is:
a) Context free
b) Not context free
c) Regular
d) None of the mentioned
Answer: b
Explanation: The pumping lemma is often used to prove that a given language L is non-context-free, by showing that arbitrarily long strings s are in L that cannot be “pumped” without producing strings outside L.
73. What is the pumping length of string of length x?
a) x+1
b) x
c) x-1
d) x2
Answer: a
Explanation: There exists a property of all strings in the language that are of length p, where p is the constant-called the pumping length .For a finite language L, p is equal to the maximum string length in L plus 1.
74. Which of the following does not obey pumping lemma for context free languages ?
a) Finite languages
b) Context free languages
c) Unrestricted languages
d) None of the mentioned
Answer: c
Explanation: Finite languages (which are regular hence context free ) obey pumping lemma where as unrestricted languages like recursive languages do not obey pumping lemma for context free languages.
0 Comments