The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
68 views
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$}
asked in Theory of Computation by Junior (567 points)
edited by | 68 views

1 Answer

+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.

answered by Loyal (6.4k points)
selected by
+1
thanks, @prateek I will apply this technique in other 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

40,861 questions
47,532 answers
145,985 comments
62,293 users