The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+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 **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 ^{m}b^{n}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

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

Now w^r becomes bbbabaaa but stack top is aba

So not CFL.

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.

- All categories
- General Aptitude 1.2k
- Engineering Mathematics 4.7k
- Digital Logic 1.9k
- Programming & DS 3.5k
- Algorithms 3k
- Theory of Computation 3.7k
- Compiler Design 1.5k
- Databases 2.8k
- CO & Architecture 2.5k
- Computer Networks 2.9k
- Non GATE 837
- Others 1.2k
- Admissions 284
- Exam Queries 398
- Tier 1 Placement Questions 17
- Job Queries 51
- Projects 7

33,718 questions

40,263 answers

114,378 comments

38,900 users