Compilers Questions and Answers MCQ– Finite Automata and Regular Expressions – 1
Questions & Answers on Compiler Introduction
The section contains questions and answers on finite automata and regular expressions, cross compilers, lexical analysis and relations.
Finite Automata and Regular Expressions
- Number of states of FSM required to simulate behaviour of a computer with a memory capable of storing “m” words, each of length ‘n’
- a) m x 2n
- b) 2mn
- c) 2(m+n)
- d) All of the mentioned
Answer
Answer: b
Explanation: For every Data here length is n and memory’s state is defined in terms of power of 2, Here the total memory capability for all the words = mn Hence the number of states is2mn.
- An FSM with
- a) M can be transformed to Numeral relabeling its states
- b) M can be transformed to N, merely relabeling its edges
- c) Both of the mentioned
- d) None of the mentioned
Answer
Answer: c
Explanation: The Definition of FSM states that M can be transformed to N by relabeling its states or its edges.
- Which of the following is right?
- a) A Context free language can be accepted by a deterministic PDA
- b) union of 2 CFLs is context free
- c) The intersection of two CFLs is context free
- d) The complement of CFLs is context free
Answer
Answer: b
Explanation: Context-free languages are closed under the following operations. The Kleene star, the concatenation, the union and the intersection.
- Consider the following two statements:
S1: { 02n |n >= l} is a regu1ar language
S2: { 0m 0n 0(m+n) l m >= 1 and n >= 2} is a regu1ar language
Which of the following is true?
- a) Only S1 is correct
- b) Only S2 is correct
- c) Both S1 and S2 are correct
- d) None of S1 and S2 is correct
Answer
Answer: c
Explanation: S1 can be written as (00)n where n >= 1. And S2 can be written as (00) (m+n) where m >=2 and n >= 1. S2 can be further reduced to (00)x where x >= 3. SO we can write regular grammars for both
G1 -> G100/00 (For S1)
G2 -> G200/000000 (For S2).
- Which of the following pairs of regular expressions are equivalent?
- a) 1(01)* and (10)*1
- b) x (xx)* and (xx)*x
- c) x+ and x+ x(*+)
- d) All of the mentioned
Answer
Answer: d
Explanation:
Rule (pq)*p=p (qp)*
Therefore–(xx*) (x*x**)
(xx*)(x*x*) [Using x**=x] (xx*)(x*) [Using x*x*=x*] (xx*) [Using x*xx*=x*)
x+
- Given a NFA with N states, the maximum number of states in an equivalent minimized DFA is at least.
(a) N2
(b) 2N
(c) 2N
(d) N!
Answer
Answer: b
Explanation: The initial state of the DFA constructed from this NFA is the set of all NFA states that are reachable from state 1 by e-moves; that is, it is the set {1, 2, and 3}. A transition from states1, 2, and 3 by input symbol 0 must follow either the arrow from state 1 to 2, or from state 3 to 4. Also, neither state 2 nor 4 have outgoing e-moves.
- Let L denotes the language generated by the grammar S – OSO/00. Which of the following is true?
(a) L = O
(b) L is regular but not O
(c) L is context free but not regular
(d) L is not context free
Answer
Answer: b
Explanation: The grammar itself is not regular but language L is regular as L can be represented using a regular grammar, for example S -> S00/00.
- Which of the following are not regular?
- a) String of )’s which has length that is a perfect square
- b) Palindromes Consisting of 0’s 1’s
- c) String of 0’s whose length is a prime number
- d) All of the mentioned
Answer
Answer: d
Explanation: Strings of odd number of zeroes can be generated by the regular expression (00) *0.Pumping lemma can be used to prove the non-regularity of the other options.
- If ? = {a, b, c, d, e, f} then number of strings in ? of length 4 such that no symbol is used more than once in a string is
- a) 35
- b) 360
- c) 49
- d) 720
Answer
Answer: b
Explanation: Here string length is 4 so we create string of length 4 by 6 values firstly we arrange any value by 6 methods. Then Remaining numbers are 5 so we can arrange them by 5 methods then remaining numbers are 4 so we arrange them by 4 methods and then 3.Thus 6*5*4*3=360
- Which one of the following statement is FALSE?
- a) Context-free languages are closed under union
- b) Context-free languages are closed under concatenation
- c) Context-free languages are closed under intersection
- d) Context-free languages are closed under Kleene closure
Answer
Answer: c
Explanation: CFL is closed under Kleene closure, concatenation, and Union
11.A regular expression enables a quick test to determine objects and text strings with undependable values.
- a) True
- b) False
Answer
Answer: a
Explanation: Because it checks for all the values and determines whether the output string matches with the given string.
12.RE can be used only for values of type string and number.
- a) True
- b) False
Answer
Answer: b
Explanation: No not for all values the string and numbers can we use the RE.
13.You can use RE, if you expect the value of a property to change in an unpredictable way each time its run.
- a) True
- b) False
Answer
Answer: b
Explanation: For every cycle the values does not change unpredictably because the type of grammar that it accepts is defined.
14. All ___________ Are automatically treated as regular expressions.
- a) Programmatic description
- b) Window
- c) Win Object
- d) Collection
Answer
Answer: a
Explanation: The programmatic description is genuinely treated as regular expression.
15. If a ‘/’ is used before a character that has no special meaning, ‘/’ is ignored.
- a) True
- b) False
Answer
Answer: a
Explanation: The backslash carries no significance and it is ignored.
