Questions tagged [context-sensitive]
The context-sensitive tag has no usage guidance.
110 questions
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
-4
votes
1
answer
106
views
Creating a context-sensitive grammar (CSG) for the language L = {anbna2n: n ≥ 1}
Need a grammar that can create this language, I am having issues getting a language to work and was looking for help.
2
votes
1
answer
23
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
74
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
120
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\}^*\ |...
- 169
0
votes
1
answer
118
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?
- 169
2
votes
2
answers
157
views
Context-sensitive grammar for function calls
Say we have context-free grammar for function declarations and calls (C-style)
...
0
votes
0
answers
49
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
67
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
118
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
2k
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 ...
- 335
-3
votes
1
answer
843
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
131
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
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
525
views
How to find context sensitive grammar for words like ww? [duplicate]
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
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
353
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-...
- 1
4
votes
1
answer
76
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
198
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
134
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
610
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
169
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) ...
- 548
1
vote
1
answer
845
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,154
-1
votes
2
answers
3k
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
40
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
166
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
57
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
119
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
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
1
vote
1
answer
1k
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
542
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
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
1
vote
2
answers
186
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
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 ...
1
vote
1
answer
71
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
123
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
323
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
57
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 ...
- 633
-4
votes
1
answer
104
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 ...
- 53
2
votes
1
answer
190
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
206
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
90
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
268
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,220
0
votes
2
answers
93
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
7
votes
1
answer
2k
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 ...
- 355
0
votes
1
answer
33
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, ...
- 277
4
votes
1
answer
120
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,584
3
votes
3
answers
188
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