1 Crore+ students have signed up on EduRev. Have you? Download the App 
Which of the following languages is generated by the given grammar?
G1 results in strings b, ab, bb, aab, abb, bbb, ... i.e
(and because only a's are not possible but only b's are)
G2 result in strings a, b, aa, ab, bb, aaa, aab, abb, bbb ... i.e
(or because only b's is possible
b,bb,bbb, , only a's are possible)
Consider the following languages:
Which one of the following is TRUE?
is Contextfree language
(push into stack, then push into stack , read and pop , when no left on stack, keep reading and pop
, when no c's left in input , and stack is empty, then accepted).
is Contextsensitive language and not contextfree. (cannot implemented by one stack)
an ambiguous grammar produces more than one parse tree for any string.. that's B..
02. Choose the correct alternatives (more than one may be correct) and write the corresponding letters only: (xix) Contextfree languages are
Context Free languages are not closed under intersection and complementation.
Choose the correct alternatives (more than one may be correct) and write the corresponding letters only:
If G is a context free grammar and is a string of lengthl in L(G), how long is a derivation of ω in G, if G is in Chomsky normal form?
Chomsky Normal Form (If all of its production rules are of the form):
where A, B and C are nonterminal symbols, a is a terminal symbol (a symbol that represents a constant value), S is the start symbol, and ε is the empty string. Also, neither B nor C may be the start symbol, and the third production rule can only appear if ε is in L(G), namely, the language produced by the contextfree grammar G.
Applying productions of the first form will increase the number of nonterminals from k to k+1 since you replace one
nonterminal (1) with two nonterminals (+2) for a net gain of +1 nonterminal. Since you start with one nonterminal, this means you need to do l1 productions of the first form. You then need l more of the second form to convert the
nonterminals to terminals, giving a total of l+(l1) = (2l1) productions.
Which of the following definitions below generate the same language as L , where
In the other two you can have any number of x and y. There is no such restriction over the number of both being equal.
If L_{1} and L_{2} are context free languages and a regular set, one of the languages below is not necessarily a context free language. Which one?
CFL's are not closed under intersection.
Define a context free languages for some υ in ( in other words, (L) is the set of prefixes of L).
Let is nonempty snd has an equal number of 0's and 1's}
Then is
Because for any binary string of 0's and 1's we can append another string to make it contain equal
number of 0's and 1's. i.e., any string over {0,1} is a prefix of a string in L.
Example:
01111  is prefix of 011110000 which is in L.
1111 is prefix of 11110000 which is in L.
01010 is prefix of 010101 which is in L.
Cfl are not closed under intersection and complement now choose the correct option so b)union and klenne closure
150 docs215 tests

150 docs215 tests
