@Shaik Masthan Brother can you explain L1 in term of the stack. Thankyou

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+5 votes

Which of the following languages are CFL?

$$L_1= \left \{ 0^n 1^m \mid n \leq m \leq 2n \right \} \\[1em] L_2 =\left \{ a^i b^j c^k \mid i=2j \text{ or } j=2k \right \}$$

$$L_1= \left \{ 0^n 1^m \mid n \leq m \leq 2n \right \} \\[1em] L_2 =\left \{ a^i b^j c^k \mid i=2j \text{ or } j=2k \right \}$$

0

we can think like, n ≤ m as L1 and m ≤ 2n as L2

finally we want L1.L2,

cfl's are closed under concatenation.

5th page of https://www.cs.ucsb.edu/~cappello/136/lectures/17cfls/slides.pdf

+10 votes

Best answer

+1

can you please tell me the idea of stack? i.e if i want to check if they are cfl with STACK ,then how should we approach?

0

@Uddlpto

to check with stack we need to check how many conditions we have to check in the given language

like for L2 here u need to check i=2j or j=2k....but u dont need to check them simultaneously so we can use one stack at a time to check the conditions...suppose instead of this u were given to check i=2j"and" j=2k..this would not have been possible with one stack...these two checking have to be done together..so u need two stacks here...

overall concept is as we know when we put a stack with FA it works like a memory to remeber things...as u keep on increasing the no of stacks...u start moving up the language hierarchy...and when this memory becomes infinte ..we enter into TM...hope it helps...

to check with stack we need to check how many conditions we have to check in the given language

like for L2 here u need to check i=2j or j=2k....but u dont need to check them simultaneously so we can use one stack at a time to check the conditions...suppose instead of this u were given to check i=2j"and" j=2k..this would not have been possible with one stack...these two checking have to be done together..so u need two stacks here...

overall concept is as we know when we put a stack with FA it works like a memory to remeber things...as u keep on increasing the no of stacks...u start moving up the language hierarchy...and when this memory becomes infinte ..we enter into TM...hope it helps...

–1 vote

Answer is 1)

1) To accept the input we will push "X" for "0" and when we will encounter "1" sim ply pop it.

In case M=N it will be same as 0^N 1^N or M>N then pop every "1" after "0".

2) here we required two memory comparison 1st for i=2j and j =2k , so this is not CFL.

- All categories
- General Aptitude 1.6k
- Engineering Mathematics 7.3k
- Digital Logic 2.7k
- Programming & DS 4.9k
- Algorithms 4.2k
- Theory of Computation 5.4k
- Compiler Design 2.1k
- Databases 4k
- CO & Architecture 3.5k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.5k
- Admissions 570
- Exam Queries 566
- Tier 1 Placement Questions 23
- Job Queries 70
- Projects 18

48,691 questions

52,776 answers

183,433 comments

68,387 users