All Questions
Tagged with context-sensitive automata
10 questions
5
votes
1
answer
1k
views
Why can't linear bounded automata accept an empty string?
The linear bounded automata (LBA) is defined as follows:
A linear bounded automata is a nondeterministic Turing machine $M=(Q,\Sigma,\Gamma,\delta,q_0,\square,F)$ (as in the definition of TM) with ...
- 1,773
2
votes
1
answer
4k
views
Difference between linear bound automata and a Turing machine
Can anyone give an example where a language can be rejected by linear bounded automata and accepted by a Turing machine. Is there any proof that a linear bounded automata is less powerful than a ...
2
votes
1
answer
240
views
What kind of languages can be recognized by a restricted one-tape deterministic Turing Machine?
During a lesson, our TA asked:
What kind of languages can be recognized by a deterministic Turing
Machine such that we can use only a tape portion that contains the input?
My thoughts:
my ...
- 187
1
vote
2
answers
1k
views
Why Linear bounded automata requires Nondeterministic Turing machine ? Why not Deterministic Turing machine?
Going through the topic of LBA, i.e., Linear bounded automata. I found that LBA requires the NTM with some constraints on tape. I found the same information from different sources. But I did not get ...
- 176
0
votes
1
answer
56
views
A context-sensite grammar for the language of sequences of two different types of parentheses with possible intersections?
Consider the language $L$ over the alphabet (,[,),]
such that any word $w \in L$ if formed as a shuffle of two (possible empty) well-formed sequence of parenthesis: one over (,) and another over [,].
...
- 103
0
votes
1
answer
562
views
Intersection between CSL and CFL?
I am trying to find a proof of A ∩ B where A is a CSL and B is a CFL.
Also I know that CFL is a strict subset of CSL. Does that mean that their intersection will give CFL. I am stuck
0
votes
1
answer
65
views
Why do non Context Free languages need more stacks?
In an example question sheet for my exams our professor included “Know to explain why for non CF languages 1 stack is not enough.”
We haven’t delved into CS and reclusively enumerable languages much ...
- 225
0
votes
1
answer
3k
views
{a^n b^n c^n | n>=1} - PDA
I just started learning context free grammar and Pushdown Automata, I tried implementing this particular language via a PDA, despite being told this language is context sensitive.
How I attempted it ...
- 3
0
votes
0
answers
121
views
How a regular language , context free language and context sensitive grammar are used in compilers to shape up the languge? [duplicate]
I know that regular language can be used for pattern matching , context free language is used for syntax matching and context sensitive for semantic or meaning of the sentence . But i have found it ...
- 329
-1
votes
1
answer
724
views
Context free grammar $\{a^n b^m c^k\; : \;k>m \; \; k>n\}$
Is this a CFL?
$$\{a^n b^m c^k\; : \;k>m \; \; k>n\}$$
When on seeing $a$'s and $b$'s I push them onto stack and as I see $ c$ as input if $ TOS$ is $b$ ,I pop them ,again if $TOS$ is a,I pop ...
- 99