Questions tagged [context-sensitive]
The context-sensitive tag has no usage guidance.
109
questions
1
vote
1
answer
18
views
Valid rules in CSG
In the book of Hopcroft-Ullman (the 1979 edition) there is a rule $Da\rightarrow aaD$ in the example of the CSL language $a^{2^i}$.
Valid rules in CSG have the form $\alpha A \beta\rightarrow \alpha\...
0
votes
1
answer
50
views
How is $\{a^m b^n c^p d^q \mid m*n=p+q\}$ context sensitive?
I have been trying to understand how the language $L = \{a^m b^n c^p d^q \mid m*n=p+q\}$) is context-sensitive?
I first encountered this question here.
Would be grateful if you could provide some ...
- 1
1
vote
1
answer
75
views
Language of equal numbers of as, bs, cs in any order not context-sensitive?
In his book "Foundations of Computing", professor Allison shows an example of "language of equal numbers of as, bs, and cs, but in any order", formally: $L = \{ w \in \{a,b,c\}^*\ |...
- 155
-1
votes
1
answer
57
views
Is { a^nb^na^n} a context-sensitive language?
The language $L_1 = \{ a^nb^nc^n \}$ is often given as an example of a context-sensitive language.
I am wondering if the language $L_2 = \{ a^nb^na^n \}$ belongs also to the same category?
- 155
2
votes
2
answers
107
views
Context-sensitive grammar for function calls
Say we have context-free grammar for function declarations and calls (C-style)
...
0
votes
0
answers
37
views
Devising a grammar for language L = { a^xb^ya^xb^y | x, y >= 0 }
I've been trying to come up with a proper grammar for this sort of language:
L = { aˣbʸaˣbʸ | x, y >= 0 }
I have failed to find a way to enforce consistent generation of terminals on either part (...
- 1
1
vote
0
answers
55
views
minimum number of non-terminals so that for all context-sensitive languages there is a non-contracting grammar
Every context-sensitive language $\subseteq \Sigma^* = \{a,b\}^*$ can be expressed using an essentially non-contracting grammar.
With just one non-terminal symbol, we can't express all context-...
- 181
4
votes
1
answer
107
views
Are the set of all Bitcoin addresses a context-sensitive language?
This started with me trying to make a regex to accept Bitcoin addresses. However, I couldn't do it. That led me to think: "is the set of all possible Bitcoin addresses even a regular language&...
- 43
0
votes
1
answer
751
views
How to prove ww^r is context free using pumping lemma for context free languages
I am having a hard time to prove it, what i know is we cannot prove that a language is regular by using pumping lemma cause even if the "pumped string" is in the language the language could ...
- 305
-3
votes
1
answer
567
views
What's grammar for a^n b^n c^n d^n
What wiil be grammar rules for the language L={a^n b^n c^n d^n; n>0}
- 1
0
votes
1
answer
112
views
Context Sensitive Grammar for $x \# x^R \# x$
This language is given.
$L = \{\; x \# x^R \# x \mid x\in \{a,b\}^*\;\}$
I have to figure out a context sensitive grammar for it.
I've tried several rules already but it's hard to make a copy of the ...
- 23
0
votes
1
answer
388
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
330
views
How to find context sensitive grammar for words like ww?
I'm studying formal languages and automata, and on the section of learning how to find productions that generates the grammar, I've done some exercises pretty well and was able to do some of the ...
0
votes
1
answer
46
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
223
views
Why is it undecidable to check the emptiness and finiteness of a context-sensitive grammar?
Context-sensitive languages have context-sensitive grammars, and context-free languages have context-free grammars. Using context-free grammars, we can decide the finiteness and emptiness of context-...
- 346
0
votes
0
answers
37
views
Why linear bounded automata emptiness and finiteness isn't decidable? [duplicate]
We know that linear bounded automata has tape size based on input size which is limited. Context-sensitive languages are accepted by LBA. My question is that if LBA has limited tape size why it's ...
- 346
4
votes
1
answer
72
views
Can you diagonalize a language out of CSL?
In recursion theory, it is possible to diagonalize a computable function out of the class of primitive recursive functions. Can you do the same with context-sensitive languages? I was thinking we ...
1
vote
1
answer
151
views
Easy-to-prove example of non-contextual language
When studying Chomsky's hierarchy of languages (starting from type 3), I find enlightening to encounter some language that can't belong to the current type but which very obviously belong to the next ...
- 131
1
vote
3
answers
124
views
A non-CFL over {a,b,c} with a non-CFL complement?
I understand uncountably many such languages exist, and the rationale for it is clear to me.
I just cannot think of one trivial, easy-to-prove example.
For instance, the complement of a^nb^nc^n is CF, ...
- 13
12
votes
2
answers
558
views
What is the closure of context-free languages under finite intersections?
Famously the intersection of context-free languages need not be context-free. On the other hand the intersection of context-sensitive languages is context-sensitive.
So this leads to the question: ...
- 121
3
votes
1
answer
151
views
Closure of context-sensitive languages under inverse language substitution
We define language substitution for a Context-Sensitive Language (CSL) $S$ over an alphabet $\Sigma$ is a map from $\Sigma$ into CSL's, for example: $f(abc) = L_1(a) L_2(b) L_3(c)$ such that (I guess) ...
- 495
1
vote
1
answer
686
views
Difficulty in understanding the proof of "Every context-sensitive language L is recursive" as given in the Peter Linz text
I was going through the automata text by Peter Linz. There I came across the proof the theorem below. I could not quite get the portion of the proof in bolds.
Every context-sensitive language L is ...
- 1,112
-1
votes
2
answers
2k
views
Context Sensitive Grammar for the language $\{a^nb^nc^n\mid n≥1\}$
I tried many grammars and so far I got this one:
\begin{align}
&S \to aXbZ \mid abc \\
&XZ \to Ybcc \\
&Xb \to bX \\
&bY \to Yb \\
&aY \to aa \mid aaX
\end{align}
Is my grammar ...
- 15
0
votes
0
answers
36
views
Deterministic CSL = semi Deterministic CSL
How can it be proven that a
deterministic CSL = semi-deterministic CSL?
Does that imply that a CSL = semi CSL?
Would I need to build a Turing machine, since a language accepted by a Turing machine is ...
0
votes
0
answers
145
views
Proof that CSL ⊊ REC
I'm trying to prove that a context sensitive language ⊊ Turing-acceptable language.
I was thinking of working out the complement of the language $A$, where $A$ consists of all words $w$ such that $M_w$...
0
votes
0
answers
21
views
generating strings from this formal grammar [duplicate]
Hey guys I am having trouble generating strings from this language, I haven't seen a grammar that looks like this and can't figure how to generate strings from this grammar, is this Context Sensitive ...
- 1
1
vote
0
answers
56
views
A Formal Grammar: defining English counting numbers?
I would like to define a grammar that produces and recognizes the counting numbers of the English language. I created the production rules below based on the assumption this is context-free, but I am ...
- 175
2
votes
1
answer
106
views
How can I show that this language is context sensitive?
I have this language $L=\{a^nb^nc^n,n\geq0\}$, I know this language is not context free, but I don't know how to show that it is context sensitive, do I have to use a PDA?
- 37
0
votes
1
answer
2k
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
1
vote
1
answer
960
views
How can we generate a grammar for $\{a^n b^n c^n d^n; n > 0\}$ if it is NOT context free?
This page on Wiki states that $\{a^nb^nc^nd^n \ | \ n > 0\}$ can not be generated by a CFG. This does not make sense to me as $\{$S $\to$ ABCD, A $\to$ aA | a, B $\to$ bB | b, C $\to$ cC | c, D $\...
- 194
0
votes
2
answers
366
views
How do Context Sensitive Grammar systems work?
The Quest: Use context sensitive grammar (CSG) to produce an equal N number of repeating a, b, and c using the alphabet {a, b, c}. For example, if N = 5 use CSG and a, b, and c to produce a result ...
- 103
1
vote
2
answers
878
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 ...
- 178
1
vote
2
answers
184
views
Is escaping a concept in CS?
I understand "escaping data" as making an exception when matching data; for example, if a program can't match data wrapped in some character/s (such as single and/or double quotes) without ...
- 45
2
votes
1
answer
3k
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 ...
1
vote
1
answer
63
views
Language of context-sensitive grammar
I have the following context-sensitive grammar:
$$
\begin{align*}
&S \to xSy \mid a \mid b \\
&Xa \to aa \\
&Xb \to bb \\
&Y \to a
\end{align*}
$$
I know what it does, as it always ...
- 13
0
votes
1
answer
115
views
Find CSG for $L = \{a^ib^jc^k \mid 0 \leq i \leq j \leq k\}$
I am trying to find a context sensitive grammar for the type-1 language
$L = \{a^ib^jc^k \mid 0 \leq i \leq j \leq k\}$
I can construct the first part with
\begin{align*}
S &\to aSbB \mid B \...
- 160
1
vote
1
answer
266
views
Context Sensitive Grammar for the language $\{ a^{2n} b^{2n+1} c^{3n} d^{n+3} \mid n \ge 1\}$
I have been trying to find a context sensitive grammar for the language $\{ a^{2n} b^{2n+1} c^{3n} d^{n+3} \mid n \ge 1\}$ for some time but I cannot get it done. Any ideas ?
0
votes
1
answer
51
views
What is the relation between a programming language and the language of its input?
I find some references say that
all the features of programming language fall within what can be captured by context-sensitive grammars. In fact, no programming language known to humankind anything ...
- 623
-4
votes
1
answer
101
views
How to find the substitutions that convert the starting sequence into the final sequence? CCC19J5
Here is Canadian Computing Competition 2019 Junior problem 5 on dmoj.ca. You can also see the original problem at cemc.uwaterloo.ca as well.
A substitution rule describes how to take a sequence of ...
- 43
2
votes
1
answer
156
views
An example of a context-sensitive grammar for a given language
Consider this language: $L = \{a^nb^ma^nb^m \mid n,m \ge 1\}$. Can we give for this language a context-sensitive grammar?
- 97
0
votes
1
answer
179
views
Examples of Regular, Context-free and Context-sensitive languages
Assume the languages:
$$
a) \, L_1 = \{ w \in \{b,c \}^* | \, w \, \text{contains 'bbc' as substring} \}
$$
$$
b)\, L_2 = \{ 1^k 0^m 1^m | k,m \in \mathbb{N} \}
$$
$$
c)\,L_3 = \{ w \in {0,1}^* | \,...
- 161
2
votes
1
answer
83
views
Show that $L:=\{(a^{k}b)^{i}|i,k \epsilon \mathbb{N}_{+} \}$ is context-sensitve. (With context-sensitive/noncontracting grammar)
I am studying for an upcoming exam and this is an old exam question from two years ago (all exams were made available through our lecturer):
Show that $L:=\{(a^{k}b)^{i}|i,k \epsilon \mathbb{N}_{+} \}...
1
vote
2
answers
216
views
Doubt regarding Chomsky Hierarchy, CFG and CSG
I was following a discussion on a website, where a fellow scholar claims that
this grammar
S→ aAa | bAb | ϵ
A→aA | bA |ϵ
is not CSG, so it should also NOT be a CFG. But this grammar properly ...
- 1,190
0
votes
2
answers
87
views
What makes a common programming language non-context-sensitive but RE?
I have a vague understanding that a (sane) programming language is RE as they are Turing-complete, being able to describe any Turing machine.
But I cannot pinpoint what aspect makes a programming ...
- 103
6
votes
1
answer
1k
views
A push-down automaton with two stacks which is equivalent to a linear-bounded automaton
It is known that a PDA with two stacks is equivalent to a TM.
On the other hand a PDA with one stack is capable to recognise only context-free languages.
Hence there is a kind of a gap between the ...
- 345
0
votes
1
answer
32
views
Given a certain context sensitive grammar, can one find out if a simpler context free grammar exists?
Given a generating grammar, is it possible to reduce it to a context free form, if one exists. One method might seem to be if the context sensitive rules can be reached from higher generating points, ...
- 275
4
votes
1
answer
108
views
Why are four context sensitive grammar (CSG) rules needed to represent AB -> CD?
In Wikipedia of Kuroda normal form, it says
A straightforward technique attributed to György Révész transforms a grammar in Kuroda's form to Chomsky's CSG: AB → CD is replaced by four context-...
- 7,395
3
votes
3
answers
158
views
How to give a context-sensitive grammar for a^nba^nba^nb?
I am struggling on this problem since days: $L = \{a^nba^nba^nb \mid n \in \Bbb N\}$. I have to give for this language a context-sensitive grammar.
- 97
0
votes
2
answers
1k
views
Are Context Sensitive Languages Turing Complete? [duplicate]
Related questions:
Can regular languages be Turing complete?
Why are Linearly Bounded Turing Machines more powerful than Finite State Automata?
https://stackoverflow.com/questions/14589346/is-c-...
- 215
2
votes
3
answers
499
views
concatenation of context sensitive and context-free is context sensitive or not?
Assume that $L_1$ is context sensitive language and $L_2$ is context free language, is the language $L_1 * L_2$ context-sensitive or not?
I almost sure that is not, but can't prove it.
- 21