test-series

Question

L,L3 is which type of language ?are L3,L CFL ?????

Answer 1

1 ) L3 = {x#w | w,x $\in$ {a,b} and x is a substring of w }
Its clear This not Regular, since here we need to compare string of x and W.
Next we look for CFL
Lets take an example, suppose x = aaab and w  = aaababbb
We start to push x into the stack, so when x end, our stack will look like

b

a

a

a

Next we encounter with #, we came to know we have reach a point after which string belong to w will appear.
Now when we see first a $\in$ w , then problem arise, since first a of x is at the bottom of stack, so we are not able to pop it, same goes for remaining string of w. So its definatly not CFL.
using similar argument you can prove L = {ww | w $\in$ {a,b} } is not CFL
But if the question be like  L = {x # w^R | w,x $\in$ {a,b} and x is a substring of w } then it will become CFL.

2) L = {a^mbⁿc^k | if(m == n) then n!=k, m,n,k > = 1}
To see whether its CFL or not we first push all the a's into the stack, then we compare a's with b's, if number of a's is equal to number of b's it means m is equal to n, so we pop an 'a' corresponding to every 'b'. Now if m and n are equal then we are at start symbol i.e z. Here problem starts, we don't have any b's left, so we can't compare n and k.  So this language is not CFL

Comments

it is possible when we have 2 stacks.

---

nice explanation.....

thank u sir ji

---

Yes, it possible if we have two stack, infact two stack pda is equivalent to turing machine.

---

Even for x#w^r,Consider w=aaababbb , x = aba

Now w^r becomes bbbabaaa but stack top is aba

So not CFL.

---

According to your example, whenever we encounter b and top of the stack is a, then we do nothing, when we first encounter a, we pop one a from top of the stack. then we check for next input symbol i.e b, we pop next b from stack, then we encounter a again we pop a from the stack, we left with initial symbol of stack, means x is a substring of w...its definately not DCFL but its CFL.

---

Yaa but it doesn't work with all inputs , can u figure out with the following inputs

x=aba, w^r=abbbabbaa ,now this string should be rejected as its not in the language.

a of x matches with a of w^r --- ok

b of x matches with b of w^r -- ok

what about next a ?

---

x=aba, w^r=abbbabbaa  that means w = aabbabbba, aba is not present in w, that means x is not a substring of w, defiantly it should reject.