The context-sensitive tag has no wiki summary.
-1
votes
1answer
57 views
Context sensitive grammar for the language $L=\{a^n b^n a^{2n} ;n\geq1 \}$ [closed]
Please help me with this...To find a context sensitive grammar for the language
$L=\{a^n b^n a^{2n} ;n\geq1 \}$
0
votes
2answers
47 views
Can this grammar be simplified?
So, I have a book here, which has an example for context sensitive grammar, and the grammar is the famous $0^n1^n2^n$ , and it has:
$$ \begin{align}
S &\rightarrow 0BS2 \mid 012 \\
B0 ...
4
votes
1answer
67 views
Type inference in compiler is context sensitive?
Have read in Compiler textbook that type inference is context sensitive. Can anyone explain why is it so? This means that we need context sensitive grammar in semantic analysis phase of a compiler ...
1
vote
1answer
43 views
Demonstrating that for every monotonic grammar there is an equivalent context-sensitive grammar
I'm trying to understand the equivalence in expressive power of formal grammars whose rules take the form:
$$ \alpha \rightarrow \beta $$ where $ |\alpha| \leq |\beta| $ (called a monotonic grammar), ...
5
votes
3answers
261 views
Can someone give a simple but non-toy example of a context-sensitive grammar?
I'm trying to understand context-sensitive grammars.
I understand why languages like
$\{ww \mid w \in A^*\}$
$\{a^n b^n c^n \mid n\in\mathbb{N}\}$
are not context free, but what I'd ...
7
votes
1answer
144 views
Are all context-sensitive languages decidable?
I was going through the Wikipedia definition of context-sensitive language and I found this:
Each category of languages is a proper subset of the category directly above it. Any automaton and any ...
1
vote
1answer
143 views
Which properties of context sensitive languages are decidable?
There are two context-sensitive languages, $L_1$ and $L_2$. Which of the following statements about them are decidable respectively undecidable?
$L_1 = \emptyset$
$L_1 = \Sigma^*$
$L_1 \cap L_2 = ...
