The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

0 votes

How to know that the language needs 1 stack or more than one stack in order to know about it is regular, context-free or not.

example

L1={$a^i b^j c^k│i<j<k$}

L2={$a^i b^j c^k│i<j \ or \ k<j$}

L3={$a^i b^j c^k│i<j \ and \ k<j$}

example

L1={$a^i b^j c^k│i<j<k$}

L2={$a^i b^j c^k│i<j \ or \ k<j$}

L3={$a^i b^j c^k│i<j \ and \ k<j$}

+3 votes

Best answer

$\boldsymbol{{\color{Blue}{ L1-CSL}}}$, as we can see I,j, k are involving with two comparison at the time ,we can't do this with one stack ,two stack is required because at a time we should have to remember two aplhabet ,so it can be done by CSL not by Cfl.

${\boldsymbol{\color{Blue}{L2-CFL}} }$, yes we can see j is involving with( i or k )one comparison at time ,so we can do this by one stack .either j is comparing with i or comparing with k one at a time ,no need of two stack .

${\boldsymbol{\color{Blue}{L3-CSL}} }$, this is almost same as first one but here j is greater than both ,here also j is involving with i and k with two comparison at a time{ j >I and j>k},so two stack required.so csl.

So remember one thing when one symbol is involving with two or more two comparison at a time then it can't be cfl.

- All categories
- General Aptitude 1.4k
- Engineering Mathematics 5.9k
- Digital Logic 2.3k
- Programming & DS 4.2k
- Algorithms 3.7k
- Theory of Computation 4.6k
- Compiler Design 1.7k
- Databases 3.4k
- CO & Architecture 2.9k
- Computer Networks 3.3k
- Non GATE 1.2k
- Others 1.3k
- Admissions 506
- Exam Queries 482
- Tier 1 Placement Questions 22
- Job Queries 64
- Projects 15

40,861 questions

47,532 answers

145,985 comments

62,293 users