Questions tagged [context-sensitive]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
4 votes
1 answer
101 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&...
0 votes
1 answer
122 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 ...
-3 votes
1 answer
66 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 votes
1 answer
84 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 ...
0 votes
1 answer
86 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
134 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
30 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 ...
  • 217
0 votes
1 answer
123 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
0 votes
0 answers
35 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 ...
  • 1
4 votes
1 answer
68 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
105 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 ...
1 vote
3 answers
95 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
9 votes
2 answers
394 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: ...
  • 91
3 votes
1 answer
102 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) ...
1 vote
1 answer
315 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 votes
2 answers
1k 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 ...
0 votes
0 answers
35 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
97 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
55 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
88 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?
  • 41
0 votes
1 answer
697 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
633 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 $\...
0 votes
2 answers
295 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
570 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 ...
  • 168
1 vote
2 answers
166 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
0 votes
1 answer
2k 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
59 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 ...
0 votes
1 answer
97 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 \...
1 vote
1 answer
185 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
48 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 ...
  • 591
-4 votes
1 answer
95 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
79 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?
0 votes
1 answer
92 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
74 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
155 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,172
0 votes
2 answers
72 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 ...
4 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 ...
0 votes
1 answer
24 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, ...
4 votes
1 answer
99 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,315
3 votes
3 answers
140 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.
0 votes
2 answers
660 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
433 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.
5 votes
1 answer
113 views

Mildly context-sensitive grammar

Consider a context-sensitive grammar $G$, such that all the productions of $G$ have the form $A\to \alpha$ or $Ab \to \alpha b$ (in other words, the left context is always empty and the right context ...
4 votes
1 answer
142 views

Is there a recommended process for designing CSGs (other than intuition)?

I understand the differences between Regular, Context-Free, and Context-Sensitive languages. Designing a Regular Grammar can be easier if you have a DFA. Designing a CFG isn't too hard for the ...
  • 207
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
0 votes
1 answer
170 views

Context sensitive language is context free

Problem of determining whether a context sensitive language is context free is undecidable. How to prove it
1 vote
1 answer
117 views

FSA for $(ab)^*(cb^n)^*$ [closed]

How can I prove that this language is regular, possibly by making a finite automata for this: $(ab)^*(cb^n)^*$, where $n\ge1$? An automaton can easily be drawn for the part $(ab)^*$, but the part $(...
3 votes
0 answers
100 views

Generating valid sentence with respect to attribute grammar

Given a context free grammar, both the algorithm for determining whether a given string is grammatical and the algorithm for producing a grammatical string in that language are well understood. To ...
  • 213
2 votes
0 answers
53 views

Intuition on what an attribute grammar can achieve

I have seen attribute grammars for a small handful of tasks: Parsing simple arithmetical expressions Type checking Checking that a variable is initialized anbncn (seems to be a favorite toy example).....
  • 213