Test: Context Free Language- 2 - Computer Science Engineering (CSE) MCQ

(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.

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.

L1 is context-free. 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 context-free. 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 context-free as it is nothing but equal number of 0's followed by equal number of 1's followed by equal
number of 0's.

L(G) = PALINDROME
baba does not belong to palindrome , so B is the answer

from Above grammar
Regular expression for G1: (x+z)⁺ + (x+z)*y(y+z)⁺

^{Regular expression for G2 :(y+z+xy)+}

Above grammar is for equal no of x and y

from Non-terminal 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

Regular grammar is either right linear or left linear. A left linear grammar is one in which there is at most 1 non-terminal on the right side of any production, and it appears at the left most position. Similarly, in right linear grammar non-terminal 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.

S→ aS
S→ aA
S→ aaAb
S→ aabAab
S→ aabbAaab
S→ aabbaab
hence d is d answer

string generated by this language is a,b,aba,bab,aabaa,.....all this strings are odd length palindromes

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 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ⁿ=cm¹ 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

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, non-terminal B is generating the second part of B choice and AA is generating the first part.