Explore topic-wise InterviewSolutions in .

The correct option is (a) LINEAR GRAMMAR

The best I can explain: A SIMPLE linear grammar is G with N = {S}, Σ = {a, b}, P with start symbol S and rules

S → aSb

S → ε

Correct CHOICE is (C) normal form

For explanation: When the production in G satisfy CERTAIN restrictions, then G is said to be in ‘normal form’.

Right option is (d) All of the mentioned

To explain I WOULD say: Besides the theoretical significance of CNF, it conversion scheme is helpful in algorithms as a preprocessing step, CYK algorithms and the BOTTOM up parsing of context free grammars.

The correct answer is (a) N, 2n-1

Explanation: If there is a STRING in the language of length between n and 2n-1 then the language is infite ELSE not. The IDEA is essentially the same for REGULAR languages.

The correct CHOICE is (c) never

For EXPLANATION I would SAY: Context free LANGUAGES are not closed under difference, INTERSECTION and complement operations.

Correct option is (a) x+1

For explanation I would say: There exists a property of all strings in the language that are of length P, where p is the constant-called the pumping length .For a FINITE language L, p is equal to the MAXIMUM STRING lengthin L plus 1.

Right CHOICE is (b) Not context free

For EXPLANATION I would say: The pumping LEMMA is often used to prove that a given language L is non-context-free, by showing that ARBITRARILY long STRINGS s are in L that cannot be “pumped” without producing strings outside L.

Right answer is (b) Greibach Normal Form

To ELABORATE: The normal form is of the format:

A->aB where the right hand side PRODUCTION tends to BEGIN with a terminal symbo, thus having no left RECURSIONS.

The CORRECT option is (a) Removal of USELESS variables

To elaborate: We USE the concept of dependency graph inorder to check, whether any of the VARIABLE is reachable from the starting variable or not.

Correct choice is (d) None of the mentioned

To explain: Inorder to SIMPLIFY the grammar all of the PROCESS INCLUDING the removal of null productions, unit productions and useless SYMBOLS is NECESSARY.

Right choice is (d) All of the mentioned

To explain I WOULD say: {a*B*c*} and (c) are regular languages while option (a) is not CONTEXT free LANGUAGE.

Correct option is (B) Pumping lemma for CONTEXT free languages

For explanation: In automata THEORY, the pumping lemma for context free languages, ALSO kmown as theBar-Hillel lemma, REPRESENTS a property of all context free languages.

Correct choice is (d) All of the mentioned

Easy EXPLANATION: in CNF, the PRODUCTION rules are of the FORM:

A->BC

A-> a

S->E

Correct answer is (C) e ∉ L(G)

For EXPLANATION I would say: Theorem: Let G = (V, T, S, P) be a CFG such thate ∉ L(G). Then there exists an equivalent grammar G’ having no e-productions.

Correct answer is (B) State true or FALSE:

For explanation I would say: A can be erased. So WHENEVER it appears on the right side of the production, replace with another production without the A.

Right option is (c) REGULAR CLOSURE

The best I can explain: We can use the properties of regular closure to prove that a language is not a context FREE language. Example: Intersection of context free language and regular language is a context free language. Proof by CONTRADICTION helps here.

Correct option is (b) CHOMSKY Normal FORM

The explanation: It requires the presence of a context free grammar into Chomsky Normal form to OPERATE. HOWEVER, every context free grammar can be CONVERTED into CNF for keeping the sense of grammar equivalent.

Correct choice is (a) Pentonnen NORMAL form

For explanation: Pentonnen Normal form(for Unrestricted grammars) is a special CASE where there is a slight MODIFICATION in the FORMAT of Kuroda Normal form.

AB->AD

A->BC

A->a

The correct answer is (b) GREIBACH Normal Form

Easy explanation: A context free GRAMMAR is in Greibach Normal Form if the right hand sides of all the production RULES start with a terminal, OPTIONALLY followed by some variables.

Right option is (d) If there is a LOOP in the dependency graph the the language is finite else INFINITE

To explain I would SAY: If we are able to DETECT a loop in the FORMED dependency graph, then the language in infinite.

Correct answer is (b) Context sensitive grammar

Best EXPLANATION: Every context sensitive grammar which does not PRODUCE an EMPTY string can be generated by a grammar in Kuroda Normal FORM.

The CORRECT option is (b) CONTEXT free language

For explanation I would SAY: If a language L1 is REGULAR and L2 is a context free language, then L1 INTERSECTION L2 will result into a context free language.

The CORRECT OPTION is (a) Triangular Table

The best explanation: A triangular table is CONSTRUCTED to facilitate the solution of membership problem using bottom up PARSING and DYNAMIC programming.

Correct option is (d) All of the mentioned

To explain: It is a theorem which STATES that, CONTEXT free languages are not closed under OPERATIONS LIKE intersection and complement.

The CORRECT ANSWER is (c) Both (a) and (B)

To explain: CYK algorithm is a PARSING algorithm for context free grammars, which employs bottom up parsing and dynamic programming.

Correct option is (c) context free

For explanation I would say: Conversely, EVERY context frr grammar can be CONVERTED into CHOMSKY Normal form and to other FORMS.

Correct answer is (d) all of the mentioned

The EXPLANATION is: We use certain algorithms to parse a context free grammar which include the most POPULAR CYK algorithm which EMPLOYS the concept of BOTTOM up PARSING and dynamic parsing.

Right choice is (a) 5

Easy explanation: The REDUCED PRODUCTION:

 S->aAa| BB|bb aCaa| baD| ABD| AA, A->aAa| bB| bb, B->bB| bb, C->aCaa| baD| abD| aa, D-> baD| abD| aa

Right option is (a) A-> A is actually a production

For explanation: The format SAYS: If A->B is a production, B is called A-derivable.Thus A to be A-derivable, a production : A-> A NEED to exist.

Right answer is (b) unambiguous

To explain I would say: With the simplification of CONTEXT free GRAMMARS, undesirable properties are INTRODUCED. It SAYS, if grammar G, before simplification is unambiguous, after simplification will ALSO be unambiguous.

The correct option is (a) A->B

The EXPLANATION: Any production of the FORMAT A-> B where A and B BELONGS to the V SET, is called Unit production.

The correct choice is (C) Both (a) and (b)

To elaborate: As the language seems to be finite, a dfa can be constructed for the same, THUS is REGULAR.

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

To explain: Context free LANGUAGES are not closed under COMPLEMENT and intersection. Thus, are called NEGATIVE PROPERTIES.

The correct answer is (B) true

For EXPLANATION: ALTHOUGH the pumping lemma provides some information about v and x that are pumped, it says little about the location of these SUBSTRINGS in the STRING t. It can be used whenever the pumping lemma fails. Example: {a^pb^qc^rd^s|p=0 or q=r=s}, etc.

Correct CHOICE is (a) A-> a| aaA| ababbAc| abbc

For explanation I would say: Using the SUBSTITUTION rules, we can simply ERADICATE what is useless and thus produce the SIMPLIFIED result i.e. A-> a| aaA| ababbAc| abbc.

The CORRECT option is (a) top-down parser

Easy explanation: GIVEN a grammar in GNF and a derivable STRING in the grammar with the length n, any top-down parser will halt at depth n. As the parameter ‘depth’ is mentioned, we will USE a top-down parser. Example-LL parser.

The correct choice is (a) A->XYZ

For explanation: For the first step, substitute B in first production as it only produces terminal and remove B production as it has already been utilized.

We GET A->xBz|xyz and now, as B has no production, we eliminate the TERMS which HOLD the variable B, thus the answer remain A->xyz.

The correct answer is (d) all of the mentioned

To explain I would say: VALIANTS algorithm is actually an extention of CYK which even computes the same PARSING table yet he showed another METHOD can be UTILIZED fro PERFORMING this operation.

Correct ANSWER is (b) uv^nw^nx^ny

The best explanation: LET L be a CFL. Then there is an INTEGER n so that for any u that belong to language L satisfying |t| >=n, there are STRINGS u, v, w, x, y and z satisfying

t=uvwxy

|vx|>0

|vwx|<=n

For any m>=0, uv^nwx^ny ∈ L

Right ANSWER is (C) Kleene

Explanation: Context free languages are closed under the FOLLOWING operation: union, kleene and CONCATENATION. For REGULAR languages, we can add intersection and complement to the list.

The correct choice is (B) EMPTY

Explanation: In the PROCESS of removing USELESS symbols, if the starting symbol is also a part, the CFL can be then termed as empty; otherwise not.

The correct ANSWER is (a) S->AB|BC|CD, A->0, B->1, C->2, D->3

Easiest EXPLANATION: We can eliminate the options on the basis of the format we are aware of: A->BC, B->b and so on.

Right answer is (a) Backus NAUR Form

To ELABORATE: Donald Knuth implied a BNF” syntax in which all definitions have such a form MAY be said to be in ”Floyd Normal Form”.

A->B|C

A->BC

A->a

The correct choice is (b) {0^i1^i|i>=0}

For EXPLANATION I would say: A positive result to the pumping lemma SHOWS that the language is a CFL and ist contradiction or NEGATIVE result shows that the given language is not a CONTEXT FREE language.

Correct ANSWER is (C) A-derivable

Easiest explanation: If A-> B is a production, B is called A- derivable.

If C is A-derivable, C->B is a production, and B ¹ A, then B is A -derivable.

No other VARIABLES are A-derivable.