1 Crore+ students have signed up on EduRev. Have you? 
(A) is wrong as a language can be context free even if it is being accepted by non deterministic
reverse}
(C) and (D) not always true as Context free languages are not closed under Complement and Intersection.
Let be a context free grammar where the rule set R is Which of the following statements is true?
It will be easy to analyze the problem if we replace terminal a and b by ( and ) respectively.
S →(S)  SS  ε
L(G) = balanced parentheses [each left parenthesis has a matching right parenthesis and are well nested ]
example () , ()(), (()), (()()()).
String () can be derived by above three way each having different derivation tree.
So G is Ambiguous
b) Concatenation of two balance parenthesis will be balanced also . eq. x = (()) y= () xy= (())().
c) We can design Deterministic PDA for L. put left parenthesis (only) in stack and pop with right parenthesis.
d) We cannot design DFA for L because we need a stack to match left parenthesis with right parenthesis.
only option C is true.
Consider the languages:
Which one of the following is TRUE?
L1 is contextfree. We count the number of 0's and check if the remaining number of 1's followed by 0's count to the initial
number of 0's.
L2 is not contextfree. Here the number of 0's and the following 1's must be same, which can be checked using a PDA. But
after that we must also ensure that the following number of 0's must be less than the previous count of 0's and 1's
(otherwise n < 0, which violates the condition for acceptance) and we cannot do these two checks using a single PDA.
L3 is again not contextfree as it is nothing but equal number of 0's followed by equal number of 1's followed by equal
number of 0's.
In the contextfree grammar below, S is the start symbol, a and b are terminals, and ϵ denotes the empty string.
The grammar generates the language
In the contextfree grammar below, S is the start symbol, a and b are terminals, and ϵ denotes the empty string
Which of the following strings is NOT generated by the grammar?
L(G) = PALINDROME
baba does not belong to palindrome , so B is the answer
The two grammars given below generate a language over the alphabet {x, y, z}
Which one of the following choices describes the properties satisfied by the strings in these languages?
from Above grammar
Regular expression for G1: (x+z)^{+} + (x+z)*y(y+z)^{+}
^{Regular expression for G2 :(y+z+xy)+}
Consider the grammar given below
Consider the following strings.
Which of the above strings are generated by the grammar ?
Above grammar is for equal no of x and y
from Nonterminal S > xB
=>xy [as B>y one y for one x]
S>xB
=> xxBB [as B >yBB one B result in one y for one x ]
S>xB
=>xyS [as B>yS one y for one x and start again]
Note :Same applies for string start with y i.e . S>yA
Consider the following grammars. Names representing terminals have been specified in capital letters.
Which one of the following statements is true?
Regular grammar is either right linear or left linear. A left linear grammar is one in which there is at most 1 nonterminal on the right side of any production, and it appears at the left most position. Similarly, in right linear grammar nonterminal appears at the right most position.
Here, we can write a right linear grammar for G1 as
(w  WHILE, o  OTHER)
So, L(G1) is regular.
Now for G2 also we can write a right linear grammar:
making its language regular.
So, both G1 and G2 have an equivalent regular grammar. But as such both these grammars are neither right linear nor left
linear and hence not a regular grammar. So, D must be the answer.
A CFG G is given with the following productions where S is the start symbol, A is a nonterminal and a and b are terminals.
Which of the following strings is generated by the grammar above?
S→ aS
S→ aA
S→ aaAb
S→ aabAab
S→ aabbAaab
S→ aabbaab
hence d is d answer
The language generated by the above grammar over the alphabet is the set of
string generated by this language is a,b,aba,bab,aabaa,.....all this strings are odd length palindromes
Which of the following languages are contextfree?
first check for L1. now look a^m&b^m and a^n&b^n must b comparable using one stack for CFL. now take a stack push all a^m in to the stack then push all b^n in to stack now a^n is coming so pop b^n for each a^n by this b^n and a^n will b comparable. now we have left only a^m in stack and b^m is coming so pop a^m for each b^m by which we can compare a^m to b^m ..we conclude that we are comparing this L1 using a single stack so this is CFG.
now for L2.this can not be done in to a single stack because m and n are not comparable we can not find when to push or pop so this is CSL.
now for L3.push all a's into stack and pop 2a 's for every b and at last we left with a single a .
bcz here aaaaabb is a valid string where m=2n+1 and n=2.So realized using single stack hence L3 is CFG.
Consider the following contextfree grammar over the alphabet ∑ = {a,b,c } with S as the start symbol:
Which one of the following represents the language generated by the above grammar?
Consider the 1st production S> abScT
This production generates equal number of (ab)'s and c's but after each c there is T which goes to T>bT
so with each c there can be one or more b's (one because of production T>b and more because of T>bT)
and these b's are independent.
For example
ababcbbcbb is the part of the langugage
and ababcbbbbbbcbb is also the part of the language so we rule out A and C both say equal number of b's after each c
In option D equal number of (ab)'s and c's is not satisfied . The only option that satisfies these 2 conditions is B
number of (ab)'s and c's is not satisfied . The only option that satisfies these 2 conditions is B
people who says this will be the string at any case
S> abcT
> abcb
no problem for i B in this case also here cm^{n}=cm^{1} means n value 1 thats it
and remember in B c is not coming eternally.it is coming until m value reaches n of b..right there
.if m=n=1 then cb stops
If G is a grammar with productions
where S is the start variable, then which one of the following strings is not generated by G ?
Consider a CFG with the following productions.
S is the start symbol, A and B are nonterminals and 0 and 1 are the terminals. The language generated by this grammar is
generates which is there in only B and D choices. D is not the answer as "00" is not generated by the given grammar. So, only option left is B and if we see carefully, nonterminal B is generating the second part of B choice and AA is generating the first part.
3 videos7 docs100 tests

Use Code STAYHOME200 and get INR 200 additional OFF

Use Coupon Code 
3 videos7 docs100 tests









