Explore topic-wise InterviewSolutions in .

The correct ANSWER is (d) All of the mentioned

For EXPLANATION: For converting RE to DFA , FIRST we convert RE to NFA (Thompson CONSTRUCTION), and then NFA is converted into DFA(Subset Construction).

Correct option is (b) Ф

Easiest explanation: By DISTRIBUTIVE PROPERTY (REGULAR expression identities), we can prove the given identity to be Ф.

Right option is (b) Pumping Lemma

To EXPLAIN: We use the POWERFUL technique called Pumping Lemma, for showing certain languages not to be REGULAR. We use ARDENS theorem to find out a regular expression out of a finite AUTOMATON.

Correct answer is (d) none of the mentioned

Best EXPLANATION: Lexical analysis is done using few tools such as lex, flex and jflex. Jflex is a computer PROGRAM that GENERATES lexical analyzers (ALSO known as lexers or scanners) and works apparently like lex and flex. Lex is commonly USED with yacc parser generator.

Correct answer is (d) L1=L2

The EXPLANATION is: FINITE STATE machine and REGULAR expression have same power to express a language.

Right answer is (b) It searches for text patterns

The explanation: The grep is a STANDARD UNIX utility PROGRAM that searches through a set of files in search of a text pattern,specified through a REGULAR expression.

The correct choice is (d) NONE of the mentioned

To explain: Regular expressions are USED by different commands in UNIX like ed, sed, grep, awk, vi, ETC. Sed stands for stream editor which is exclusively used for executing SCRIPTS.

The CORRECT ANSWER is (d) All of the mentioned

The EXPLANATION is: NONE.

Right CHOICE is (B) (a*b*)*

For EXPLANATION I would say: NONE.

The correct ANSWER is (d) All of the mentioned

Easiest EXPLANATION: All are EQUIVALENT to union operation.

Right option is (C) (0+01)*(1+01)

To explain I would SAY: (a) and (b) are the general cases where we restrict the acceptance of a string witrh substring 00 but we ignore the case where the string needs to end with 1 which therby, does not allows the acceptance of e.

Correct CHOICE is (a) Statement: A regular EXPRESSION is a sequence of characters that represent a pattern.

Easiest explanation: Such a generated pattern COULD be a FIXED WORD or describe something like more general.

Correct CHOICE is (a) State true or false?

To explain I would say: Lowercase letters NEAR the beginning of an ALPHABET, a, B and so on are terminal symbols. We shall also assume that digits and other characters such as + or parenthesis are TERMINALS.

The CORRECT answer is (c) Both (a) and (b)

To elaborate: A regexp processor TRANSLATES the syntax into internal representation which can be executed and matched with a string and that internal representation can have SEVERAL approaches LIKE the ONES mentioned.

Correct choice is (b) Every LANGUAGE defined by a REGULAR expression can be represented using a DFA

To ELABORATE: Using NFA with e moves, we can represent all the regular expressions as an automata. As regular expressions include e, we need to usee moves.

Correct option is (b) R*

The explanation: The given diagram represents the KLEENE operation over the REGULAR Language R in which the final states BECOME the initial and the initial state BECOMES final.

The correct answer is (a) To build the UNIFORM symbol table

To explain I would SAY: Lexical analysis involves the following task:

a) Building a uniform symbol table

b) Parsing the SOURCE CODE into tokens

c) Building a literal and identifier table

Correct option is (b) Dot

Explanation: TWO OPERANDS are SAID to be performing Concatenation operation AB = A•B = {xy: x ∈ A & y ∈ B}.

The correct CHOICE is (c) DFA to Regular Expression

Explanation: We USE this algorithm to simplify a finite automaton to regular expression or vice versa. We ELIMINATE states while CONVERTING a given finite automata to its corresponding regular expression.

The correct ANSWER is (c) Regular Languages

Easiest EXPLANATION: A FINITE automaton accepts the languages which are regular and for which a DFA can be constructed.

The CORRECT option is (d) All of the mentioned

Explanation: oolex, flex, lex, jflex, all are lexical ANALYZER TOOLS which PERFORM the following function.

Correct OPTION is (b) Matches the end of lines

For explanation: Regular expression provides more flexibility while MATCHING string patterns. SPECIAL characters LIKE ^, $, *, . are very useful.

Right choice is (b) sequence of alphanumeric CHARACTERS in a TOKEN

Explanation: A LEXEME is a STRING of characters that form a syntactic unit. It is REASONABLE to say that is the sequence of alphanumeric characters in a token.

Right answer is (c) 12

Explanation: string of length 0 = Not possible (because y is ALWAYS present).

string of length 1 = 1 (y)

string of length 2 = 3 (XY,YY,ya)

string of length 3 = 8 (XXY,xyy,yxy,yyy,YAA,yab,xya,yya)

Correct answer is (a) (ab U a) *

To EXPLAIN: The Regular expression (ab U a) * is converted to NFA in a SEQUENCE of stages as it can be CLEARLY SEEN in the diagram. This NFA consist of 8 stated while its minimized form only contains 2 states.

Correct answer is (a) true

Best explanation: For every state which is eliminated, a NEW regular EXPRESSION is produced. The NEWLY GENERATED regular expression act as an input for a state which is next to REMOVED state.

Correct choice is (a) Perl

The explanation is: Many languages COME with built in support of REGEXPS like Perl, Javascript, Ruby ETC. While some provide support using STANDARD LIBRARIES like .NET, Java, Python, C++, C and POSIX.

The correct answer is (c) Regular & RATIONAL Expression

For explanation I would say: In automata theory, Regular Expression(SOMETIMES also called the Rational Expression) is a SEQUENCE or set of CHARACTERS that define a search pattern, mainly for the use in pattern matching with strings or string matching.

Right OPTION is (c) R, L(R)

The best EXPLANATION: When we WISH to distinguish between a REGULAR expression R and the language it represents; we write L(R) to be the language of R.

The correct choice is (a) (x-y)-Z

The best I can explain: In ARITHMETIC, we GROUP two of the same operators from the left, HENCE x-y-z is EQUIVALENT to (x-y)-z and not x-(y—z).

The correct CHOICE is (d) all of the mentioned

Easy explanation: A PROGRAM which performs lexical analysis is called lexer, scanner or lexer. Nowadays, lexer is COMBINED with a parser which allows syntactic analysis.

The correct choice is (a) gray|grey

To ELABORATE: PARANTHESIS can be used to DEFINE the scope and precedence of OPERATORS. Thus, both the expression represents the same PATTERN.

Right OPTION is (B) Every finite subset of non-regular set is regular

For EXPLANATION: None.

The CORRECT CHOICE is (a) (1+0+e)6

Best explanation: As the input variables are under Kleene Operation, we NEED to include e,thus option c is not correct,thereby option (a) is the right answer.

Right answer is (d) None of the mentioned

To explain: It does not matter in which order we group the expression with the OPERATORS as they are associative. If one GETS a chance to group the expression, one should group them from left for convenience. For INSTANCE, 012 is grouped as (01)2.

The correct choice is (d) a+ ((B*).C)

Easiest explanation: Following the RULES of precedence, KLEENE or star operation would be done FIRST, then concatenation and finally union or plus operation.

Correct OPTION is (b) It takes no auxiliary memory

Easiest explanation: A LANGUAGE is regular if and only if it can be accepted by a FINITE automaton. Secondly, It supports no concept of auxiliary memory as it loses the data as soon as the device is SHUT down.