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

0

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.

0

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.3k
- Engineering Mathematics 5.2k
- Digital Logic 2k
- Programming & DS 3.7k
- Algorithms 3.2k
- Theory of Computation 4k
- Compiler Design 1.6k
- Databases 3k
- CO & Architecture 2.6k
- Computer Networks 3k
- Non GATE 1k
- Others 1.3k
- Admissions 487
- Exam Queries 436
- Tier 1 Placement Questions 18
- Job Queries 56
- Projects 9

36,194 questions

43,647 answers

124,088 comments

42,929 users