The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+1 vote
39 views

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

asked in Theory of Computation by Boss (6k points)
edited by | 39 views

1 Answer

+2 votes
Best answer

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 = 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 # wR | w,x $\in$ {a,b} and x is a substring of w } then it will become CFL.

2) L = {ambnck | 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

answered by Boss (6.6k points)
edited by
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.

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

29,167 questions
36,992 answers
92,219 comments
34,837 users