Explore topic-wise InterviewSolutions in .

The CORRECT answer is (a) LEXEME

The EXPLANATION is: A lexeme is a STRING of characters that form a syntactic UNIT.

The correct option is (c) TOKENIZATION

The best explanation: The PROCESS of forming tokens from an input stream of CHARACTERS is called tokenization.

The correct ANSWER is (d) All of the mentioned

The best EXPLANATION: All of them along with OPERATORS are different TYPES of LEXEMES.

The CORRECT OPTION is (B) B

The explanation is: The GIVEN alphabet contains only one SYMBOL {a} and the given NFA accepts all strings with any number of occurrences of ‘a’.

Correct answer is (d) None of the mentioned

For explanation I would say: In a two-phase COMPILER, ensures that there is a SOURCE PROGRAM and an OBJECT program.

Right choice is (a) L1 is regular but not L2

The best EXPLANATION: L1 is regular let us considering the string 011011011011 . Number of times 011 has occurred is 4but also its occurrence is 3. Also if the string is ending with 011we can make a 110 . Now the next string: 110110110110 in this 110 has occurred 4 times and 011 3 times which already satisfy the .

The correct ANSWER is (a) The code generator

Explanation: LEXICAL ANALYSIS is the process of converting a sequence of CHARACTERS into a sequence of tokens.

The CORRECT OPTION is (a) (a+b)* bbbb (a+b)*

To explain: Out ofall RE MENTIONED only the first stringcertainly has bbbb as SUBSTRING. Rest all just have a possibility of having it.

Correct OPTION is (C) 2N

For explanation I would say: If the NFA has n states, the resulting DFA may have up to 2n states, an exponentially larger number, which sometimes makes the CONSTRUCTION IMPRACTICAL for large NFAs.

Correct choice is (C) SCANNER

Explanation: A compiler’s scanner reads an INPUT stream that consists of characters and produces an OUTPUT stream that contains words, each labelled with its Syntactic category.

Correct answer is (b) L1 = {0, 1}* – L

For explanation I WOULD say: Either it TAKES 0 or 1 or iterations of it or none.compilers-questions-answers-Obtaining the regular Expression from the FINITE autom

Correct CHOICE is (C) All of the mentioned

To elaborate: S => a. A string of length 2 has only one DERIVATION, e.g., S => SS => aS => ab.

The CORRECT answer is (a) True

Easiest EXPLANATION: An NFA is NOTHING more than an ε-NFA with no ε TRANSITIONS. Thus • δ (q, ε) for all STATES q = ∅.

Right answer is (a) Optimizer

For EXPLANATION: The optimizer is an IR-to-IR TRANSFORMER that tries to IMPROVE the IR program in some WAY.

The correct choice is (a) True

The explanation is: NFA-ε can be transformed into a NFA ALWAYS, the PROPERTIES are ALSO true for NFAs.

The correct choice is (a) True

To explain I would SAY: Therefore it is possible to convert an existing NFA into a DFA for the PURPOSE of implementing a simpler machine. Which is executed by using the POWERSET construction.

The correct choice is (b) All odd length PALINDROMES

The best EXPLANATION: The STRINGS accepted by language are {a, b, aaa, BBB, ABA, bab,}. All the strings are odd length palindromes.

The correct CHOICE is (b) An FSM cannot FIX the midpoint

To elaborate: Palindromes cannot be RECOGNIZED by FSM.

The correct option is (b) Q X Σ→2Q

To EXPLAIN: Let Q be a FINITE SET and let be a finite set of symbols. Also let be a function from Q to 2Q. All the elements of Q a state, the transition function, q0 the initial state and A the set of accepting states.

Then a nondeterministic finite automaton is a 5-tuple < Q,, q0,, A >.

Correct CHOICE is (B) No

The explanation is: It adds NOTHING NEW to the automata.

Right choice is (a) True

Easiest explanation: YES ordinary NFA and NFA-ε are the same, in that, given either one, one can CONSTRUCT the other, which recognizes the same LANGUAGE.

Correct OPTION is (c) For a regular expression R, there does not EXISTS NDFA with L® ant transit that accept

To explain I would SAY: The vice versa is TRUE.

The CORRECT option is (B) Requires the subset construction

To explain I would SAY: In order to convert NDFA to DFA we work with sets of state where each state in the DFA corresponds to a set of NFA states.

Right answer is (b) NULL string

To ELABORATE: Null STRINGS are not accepted by FINITE AUTOMATA.

Correct choice is (d) Complement

Easiest EXPLANATION: Explanation: RE are CLOSED under

Union (CF. picture)

Intersection

Concatenation

Negation

Kleene CLOSURE.

Right OPTION is (c) OUTPUT depends on PRESENT state and present input

Easy explanation: The definition states that its output is DETERMINED by current state and current input.

Correct ANSWER is (a) ∑, Q, q0, F, δ

The explanation: An NFA is represented formally by a 5-tuple, (Q, Σ, Δ, q0, F), of

aset of STATES Q

a set of INPUT symbols Σ

a transition function Δ : Q × Σ → P(Q).

an initial state q0 ∈ Q

afinal state F ⊆ Q.

The correct ANSWER is (a) It cannot be REACHED anytime

Explanation: The very MEANING of in accessible state is that it cannot be reached at any POINT of TIME.

The CORRECT CHOICE is (a) True

The EXPLANATION is: Empty strings can be inputted n a NDFA.

Correct CHOICE is (b) S->aSb/ab

For explanation I would SAY: generates the set {an BN, n=1,2,3 ….}which is not REGULAR.

Right answer is (a) True

For EXPLANATION I WOULD SAY: The ε-closure of a set of states Z of an NFA is defined as the set of states reachable from any state in Z following ε-transitions.

The CORRECT answer is (C) {a,b}

The explanation: EITHER a is the output or b HENCE it’s {a, b}.

Right CHOICE is (b) SET of SYMBOLS over Σ

Easiest explanation: The definition of the GRAMMAR is set of symbols over Σ.

Right choice is (c) If control enters no way to come out from the STATE

To elaborate: It is a rejecting state for if the control enters it REACHES the DEAD end and cannot REACH an accepting state.

Correct choice is (a) MINIMIZATION of DFA

The best I can EXPLAIN: Myhill–Nerode theorem PROVIDES a necessary and sufficient condition for a LANGUAGE to be regular. The Myhill–Nerode theorem can be generalized to trees. And used for minimization of DFA.

Correct ANSWER is (b) NEXT state

Easiest EXPLANATION: The definition states that its output is DETERMINED by current state and current INPUT.

Correct option is (d) Regular Language

Best EXPLANATION: All regular languages are IMPLEMENTED by FINITE AUTOMATA.

The correct OPTION is (c) =

To elaborate: The no of LANGUAGES accepted by NFA and DFA is EQUAL.