Explore topic-wise InterviewSolutions in .

Right ANSWER is (B) true

Easy explanation: There exists SUBSEQUENT steps like formation of epsilon-NFA and NFA before the formation of corresponding DFA.

Right answer is (c) Both (a) and (b)

EXPLANATION: Using closure properties we can give a=solution to MANY problems like :

Is the regular languages L1 and L2 closed on CONCATENATION operation?, ETC.

The correct option is (d) All of the mentioned

Explanation: It is possible to CONVERT from one specification to ANOTHER. We can EXPRESS a regular LANGUAGE in all the GIVEN four variants.

Right answer is (d) All of the mentioned

For explanation: Emptiness, Infiniteness and Membership are the decision PROPERTIES of any language CLASS. Example: Is the language L empty? Or Is w, a string belongs to the REGULAR language L?

Correct choice is (d) None of the mentioned

Best explanation: To GIVE a solution to the mentioned problems, we require decision properties and for some, we need ADDITIONAL tools LIKE minimized automaton and Pumping lemma.

The correct answer is (d) Membership

Explanation: Membership is a decision property of language class while OTHERS MENTIONED LIKE Kleene, Reversal and HOMOMORPHISM are Closure PROPERTIES of language class.

Correct ANSWER is (b) PUMPING

The EXPLANATION is: The PROCESS of repeatation is CALLED pumping and so, pumping is the process we perform before we check whether the pumped string belongs to L or not.

The CORRECT option is (a) L

Explanation: (L’)’ is equivalent to L and L U L is SUBSEQUENTLY equivalent to L.

Correct answer is (a) Subset CONSTRUCTION method

The EXPLANATION is: Powerset or subset construction method is a standard method for converting a non deterministic finite automata into DFA which recognizes the same FORMAL language.

The correct answer is (d) All of the mentioned

Best EXPLANATION: There are several applications of pigeonhole principle:

Example: The SOFTBALL team: Suppose 7 people who want to play softball(n=7 items), with a limitation of only 4 softball teams to choose from. The pigeonhole principle tells US that they cannot all play for different teams; there must be atleast one team featuring atleast two of the seven players.

Right choice is (a) linear

Explanation: It is possible to parse the expression efficiently, using a technique that TAKES only O(N) TIME on a expression of LENGTH n^3.

The correct choice is (d) All of the mentioned

Explanation: While constructing DFA B, we NEED to take care of the following:

a) The same SET of states

b) The same START state

c) The same final state

d) INPUT alphabet = the symbols to which HOMOMORPHISM h applies.

The CORRECT CHOICE is (C) 3

Easiest explanation: We select a STRING w such that w=xyz and |y|>0 and other conditions. However, there exists an integer n such that |w|>=n for any wÎL.

Correct OPTION is (a) PROOF by contradiction

For explanation: We use the method of proof by contradiction in pumping lemma to PROVE that a LANGUAGE is REGULAR or not.

Right answer is (d) All of the mentioned

The EXPLANATION: L^r, L’, L* i.e. REVERSAL, complementation and kleene all are the CLOSURE properties of REGULAR language.

The correct answer is (b) CLOSED

For EXPLANATION I would SAY: If two regular languages are closed under an operation OP, then the resultant of the languages over an operation op will ALSO be regular.

The correct option is (c) Both (a) and (b)

EASY explanation: On the contrary, the typical way to PROVE that a language is to CONSTRUCT either a finite STATE machine or a regular expression for the language.

The correct answer is (a) n

For EXPLANATION I would SAY: The conversion DFA to NFA is simple, and takes O(n) TIME on an n-state DFA.

Correct answer is (b) G^rF^r

The EXPLANATION: If E= FG, E^r=G^rF^r . EXAMPLE: (01*)R=(1*)R(0)R

Correct OPTION is (a) REGULAR

To explain I WOULD say: If L is regular so is its complement, if L’ is regular so is its reverse, if (L’)^R is regular so is its Kleene.

The correct choice is (d) None of the mentioned

To explain I would say: Each of the FOLLOWING can expressed in TERMS of ordinary NFA with DIFFERENT time COMPLEXITIES.

The correct OPTION is (d) Al of the mentioned

For explanation I WOULD say: At FIRST STAGE 1/2 L will be regular and subsequently, all the OPTIONS will be regular.

Correct ANSWER is (c) no object

Explanation: This is one of the alternative formulations of the pigeon hole PRINCIPLE. As n < m, there will exist some PLACE which will not receive any of the object.

The correct choice is (a) string count

Best explanation: Given: w =xyz. Here, xyz individually represents STRINGS or RATHER substrings which wecompute over conditions to CHECK the REGULARITY of the language.

Right option is (d) All of the mentioned

Best explanation: REGULAR LANGUAGES are CLOSED under the FOLLOWING operations:

a) Regular expression operations

b) Boolean operations

c) HOMOMORPHISM

d) Inverse Homomorphism

Right option is (C) L^r

The best explanation: L^r is defined as the REVERSAL of a language. L^ris a set of strings whose reversal is in L.

Example: L={0, 01, 100}

Lr={0, 10, 001}

The correct answer is (c) quadruple

The explanation: We can quadruple the size of the REGULAR expression per ROUND. Thus, we can SIMPLY write n^3 expressions can TAKE time O(n^34^n), where n =number of states of the DFA.

Right CHOICE is (a) exponential time

The best explanation: We can eliminate e-transitions from an n STATE epsilon-NFA to BUILD an ordinary NFA in O(n^3) time, without CHANGING the number of states.Next, producing to DFA can take exponential time.

The CORRECT option is (c) (ab)*

Easy EXPLANATION: abe*+e(ab)*(Using the IDENTITIES e=e*, eE=Ee=E)

=ab+(ab)*=> ab will contain inside (ab)*, THUS =>(ab)*.

Correct answer is (c) both (a) and (B)

Explanation: COLLISIONS are inevitable in a HASH table because the number of POSSIBLE keys exceeds the number of INDICES in the array.

The correct option is (a) n

Easy explanation: It is the first CONDITIONAL statement of the lemma that states that |xy|<=n, i.e. the MAXIMUM length of the SUBSTRING xy in w can be n only.

The correct choice is (a) x=p, y=QR, z=s

The BEST I can EXPLAIN: The FSA accepts the string pqrs. In TERMS of pumping lemma, the string pqrs is broken into an x portion an a, a y portion qr and a z portion s.

Correct option is (d) All of the mentioned

For explanation: Homomorphism on an aphabet is a FUNCTION that gives a STRING for each SYMBOL in that alphabet. Example: h(0)=ab, ETC.