Timeline for Which class of languages is accepted by PDA when we restrict the stack to logarithmic size?
Current License: CC BY-SA 3.0
3 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 2, 2015 at 5:02 | comment | added | Doralisa | I didn't conclude that there is no language in logcf over two characters. I conclude that there is is no non-regular over two character is in logcf. I mean all languages over two alphabet in this class are regular. regular languages use finite cells of stack(and even we can make PDA for them without using its stack) | |
| Feb 1, 2015 at 19:42 | comment | added | Fatemeh Ahmadi | you claimed that every language over 0,1 that is in logcf, at most uses log|w| cells of stack, hence the relation of n(0) and n(1) is nonlinear. so it is not cf , hence is not in logcf. From what you have said one can conclude that there is no language in logcf over two characters, so you confine logcf to the one-character-languages. | |
| Feb 1, 2015 at 17:52 | history | answered | Doralisa | CC BY-SA 3.0 |