Explore topic-wise InterviewSolutions in .

Correct choice is (d) NONE of the mentioned

To explain: All of the GIVEN languages are regular and finite and thus, can be REPRESENTED using respective deterministic finite automata. We can ALSO use mealy or moore machine to represent remainders for OPTION c.

The CORRECT answer is (b) Statement 1 is assertion, Statement 2 is the solution

For EXPLANATION: The Longest MATCH rule states that the lexeme scanned should be determined on the basis of longest match among all the token available.

The correct option is (b) True

To explain: 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.

Right option is (d) none of the mentioned

For explanation: Regexp processors are found in SEVERAL search engines, seach and REPLACE mechanisms, and text PROCESSING utilities.

Right CHOICE is (a) Yes

For explanation: The STATE q2 can be ELIMINATED with ease and the reduced state DIAGRAM can be represented as:

The correct choice is (b) {w | w is a string of length multiple of 3}

Best explanation: This regular EXPRESSION can be used to ELIMINATE the answers and get the result. The length can be even and as WELL more than 3 when R= (∑∑∑) (∑∑∑) (particular case).

Correct answer is (a) 0

The best EXPLANATION: An annihilator for an operator is a value such that when the operator is applied to the annihilator and some other value, the RESULT is the annihilator.

The correct OPTION is (c) (AB)* and a*b*

For EXPLANATION: (ab)*=(a*b*)*.

Correct option is (c) Kleene, Dot, Union

To elaborate: If a regular language expression is GIVEN, the appropriate order of PRECEDENCE if the PARENTHESIS is IGNORED is: STAR or Kleene, Dot or Concatenation, Union or Plus.

Correct choice is (a) (0+1) *(00+11) (0+1) *

BEST explanation: The transition states shown are the result of breaking down the given regular expression in fragments. For dot operation, we CHANGE a state, for union (PLUS) operation, we diverge into two TRANSITIONS and for Kleene Operation, we apply a loop.

Correct option is (C) Both (a) and (b)

To explain: In automata theory, the Myphill Nerode THEOREM provides a necessary and SUFFICIENT CONDITION for a language to be regular. The Myphill Nerode theorem can be used to show a language L is regular by proving that the number of equivalence CLASSES of RL(relation) is finite.

The correct answer is (B) Let L be a regular language. If ~L has K equivalent classes, then any DFA that recognizes L must have ATMOST k states.

Explanation: Let L be a regular language. If ~L has k equivalent classes, then any DFA that recognizes L must have atleast k states.

Correct choice is (b) DFA-regular

To elaborate: This is a simple example of a closure property: a property saying that the SET of DFA-regular LANGUAGES is CLOSED under CERTAIN operations.

Correct OPTION is (d) None of the mentioned

Easiest explanation: A quantifier after atoken SPECIFIES how often the preceding element is allowed to occur. ?, *, +, {n}, {min, }, {min, MAX} are few quantifiers we use in regexps IMPLEMENTATIONS.

The CORRECT ANSWER is (a) ϵ

To ELABORATE: NONE.

The CORRECT OPTION is (a) Brzozowski METHOD

The explanation: Brzozowski method takes a unique approach to generating regular EXPRESSIONS. We create a SYSTEM of regular expressions with one regular expression unknown for each state in M, and then we solve the system for Rλ where Rλ is the regular expression associated with starting state qλ.

The correct choice is (b) 3

Best explanation: It is not required to automate the question if ASKED theoretically.The number of zeroes FIXED is 2. Therefore, we can REPRESENT the REGULAR expression as 1*01*01*.

Correct option is (a) EQUIVALENCE

The explanation is: According to MYHILL Nerode theorem, the corollary proves the GIVEN statement correct for equivalence CLASSES.

The correct OPTION is (a) RULE priority

To explain I WOULD say: 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.

Correct answer is (d) /^$/

The explanation: There are few expressions which provide the utility of MATCHING metacharacters INCLUDING /^$/ for blank lines,/ */ for matching one or more spaces, /^.*$/ for matching an entire LINE whatever it is.

The correct ANSWER is (d) (0+1+ε)^4

To elaborate: The extended notation would be (0+1)^4 but however, we MAY allow some or all the FACTORS to be ε. Thus ε NEEDS to be included in the given regular expression.

Correct OPTION is (d) All of the mentioned

Explanation: There are two approaches to infer that certain string are in the language of a certain variable. The most CONVENTIONAL way is to use the rules from body to head, recursive inference. The second APPROACH is expanding the starting variable using one of its productions whose head is tart symbol and derive a string consisting ENTIRELY of terminals(head to body or derivations).

The correct choice is (d) none of the mentioned

For explanation: 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.).

The correct choice is (d) WhiteSpace

The BEST EXPLANATION: The lexical analyzer IGNORES all the whitespaces and fragments the program into tokens.

Right answer is (a) Expressions are juxtaposed

Easy explanation: DOT operation or concatenation operation MEANS that the TWO expressions are juxtaposed i.e. there are no intervening operators in between. In fact, UNIX regular expressions use the dot for an ENTIRELY different purpose: representing any ASCII character.

Right choice is (a) Create the NFA using Null moves

To explain: Two steps are to be FOLLOWED while converting a regular expression into a transition DIAGRAM:

a) CONSTRUCT the NFA using null moves.

b) Remove the null transitions and convert it into its equivalent DFA.

Correct choice is (a) {0, 1, 01, ε}

Easy EXPLANATION: The REGULAR expression is fragmented and the SET of the strings eligible is FORMED. ‘+’ represents UNION while ‘.’ Represents concatenation.

The CORRECT choice is (d) All of the mentioned

The EXPLANATION is: The myphill nerode theorem can be generalized to trees and an application of TREE automata prove an algorithmic meta theorem about GRAPHS.

The correct choice is (a) ε

The best I can explain: The star operation BRINGS together any NUMBER of strings from the language to get a string in the result. If the language is empty, the star operation can put together 0 strings, resulting only the empty string.

Right answer is (a) (0+1)*001(0+1)*

The best explanation: There needs to be 001 TOGETHER in the string as an ESSENTIAL substring. Thus, the other components can be ANYTHING, 0 or 1 or E.

Right CHOICE is (d) (t*r*)

To explain: As Kleene OPERATION is not on the whole of the substring, it will not REPEAT and MAINTAIN the ORDER of t, r.

Right option is (c) Non-null transitions

Easy explanation: Arden’s THEOREM strictly assumes the following;

a) No null transitions in the TRANSITION diagrams

b) True for only SINGLE initial state

The CORRECT option is (d) None of the mentioned

Easiest explanation: There are at least three algorithms which decides for us, whether and how a regexp matches a string which included the TRANSFORMATION of Non deterministic automaton to deterministic finite automaton, The lazy DFA algorithm where ONE simulates the NFA DIRECTLY, building each DFA on DEMAND and then discarding it at the next step and the process of backtracking whose running time is exponential.

The correct option is (a) Statement: The STATE removal approach identifies patterns within the graph and removes state, building up REGULAR expressions along each transition.

For EXPLANATION: This METHOD has the advantage over the transitive CLOSURE technique as it can easily be visualized.

Right choice is (b) MATCHES no or one OCCURENCE of the capital LETTER X.

For explanation I would say: There are manyother common regular expression operators like $, ^, ETC. Which have their own respective purposes.

The correct answer is (B) Unify single TRANSITIONS to multi transitions that contains union of input

For explanation I would SAY: While eliminating the states, we unify multiple transitions to ONE transition that contains union of input and not the vice VERSA.

The correct ANSWER is (d) RФ=R

For explanation I WOULD say: There are few identities over Regular EXPRESSIONS which INCLUDE: RФ=ФR=Ф≠R

Right option is (d) Lexical Analysis

The best I can explain: 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.

The correct CHOICE is (c) generates an error

To explain I would say: 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.

Correct choice is (d) more than one option is correct

Best explanation: If there is more than one ACCEPTING STATE or if the single accepting state as an out degree , ADD a new accepting state, make all other states non accepting, and hold an e-transitions from each FORMER accepting state to the new accepting state.

Right answer is (c) (110+11)*0

To explain I would say: There is no STATE change for union operation, but has two different paths while for concatenation or dot operation, we have a state change for EVERY element of the STRING.

Right OPTION is (B) [(0+1)-(0b+a1)*(a+b)]*

EXPLANATION: EXCEPT b all are regular expression*.