Questions tagged [context-sensitive]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0
votes
0answers
28 views

What is the most commonly used/ most practical method to parse context sensitive languages?

what is the most commonly used / most practical method to parse CSLs ? By "most practical" I mean Not too theoretical but in opposite to that, with practical usecases Not too complicated (...
0
votes
0answers
32 views

What kind of automaton recognizes closed terms of the lambda calculus?

There seems to be an interesting model of computation involved in determining whether a term from some programming language has any free variables. It's a tree traversal that seems almost like the ...
0
votes
0answers
20 views

Building Context sensitive grammars?

I just discovered Context-sensitive grammars. The problem is most of the examples are weird non-interesting toy languages ! Second the descriptions are math oriented, rather than programmer oriented. ...
2
votes
1answer
63 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?
0
votes
1answer
58 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 ...
1
vote
1answer
34 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
2answers
98 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 ...
1
vote
2answers
90 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 ...
1
vote
2answers
101 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 ...
0
votes
1answer
581 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
1answer
32 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
1answer
23 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
1answer
51 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 ?
1
vote
1answer
37 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 ...
-4
votes
1answer
78 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 ...
2
votes
1answer
51 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
1answer
37 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}^* | \,...
2
votes
1answer
52 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
2answers
86 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 ...
0
votes
2answers
57 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
1answer
601 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
1answer
21 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
1answer
80 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-...
4
votes
3answers
111 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
2answers
245 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-...
2
votes
3answers
260 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
1answer
65 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
1answer
76 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 ...
0
votes
0answers
80 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 ...
0
votes
1answer
104 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
1answer
91 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
0answers
94 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 ...
2
votes
0answers
41 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).....
2
votes
0answers
241 views

Context-sensitive grammar for language $L = \left\{ww \mid w \in \left\{a,b\right\}^* \right\}$ [duplicate]

Find a context-sensitive grammar for language $L = \left\{ww \mid w \in \left\{a,b\right\}^* \right\}$ where $L \in DCSL \setminus CFL$. I find this task from old exam but there is no solution. I try ...
2
votes
1answer
131 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 ...
10
votes
4answers
449 views

A language in NSPACE(O(n)) and very likely not in DSPACE(O(n))

Actually I found that the set of context-sensitive Languages, $\mathbf{CSL}$ ($\mathbf{=NSPACE(O(n)) = LBA}$ accepted languages) are not so widely discussed as $\mathbf{REG}$ (regular languages) or $\...
1
vote
2answers
213 views

Why do derivation tree not make sense for context-sensitive grammars?

I don't understand the line in the paper "Mappings and Grammars on Trees" by William C. Rounds, the passage: Transformational theory, as developed by Chomsky [7] and many others, deals with the ...
0
votes
2answers
1k views

Context sensitive grammar for $\{a^{2^n}\mid n\geq 0\}$

I want to build a context sensitive grammar for the language $\{a^{2^n}\mid n\geq 0\}$. I think it should be something like this \begin{align*} S &\to aA \mid a\\ aA&\to aaaA \mid aa \end{...
1
vote
1answer
660 views

Is union of context-free and non-context-free languages non-context-free?

It is known that union of two context-free languages is also context-free. But how about union of context-free and non-context-free languages?
2
votes
2answers
2k views

Examples of Context-sensitive grammars which produces non-indexed language

Well known example of Context-sensitive grammar which produces language $\{a^nb^nc^n|n\geq 1\}$ is widely used in various papers. But actually, while this language is definitely context-sensitive, it ...
4
votes
1answer
133 views

Is every language in PTime also context-sensitive?

Context-sensitive languages are exactly those that can be recognised using linearly bounded automata, i.e., those in NSPACE(O($n$)). This subsumes all languages that can be recognised in linear time, ...
8
votes
1answer
270 views

Is unary language with polynomial power context sensitive?

I suppose that $\Sigma = \{a\}$. Prove or Disprove: For every polynomial $p(n)$ with coefficients in $\mathbb{N}$, $L = \{a^{p(n)} \; | \; n \in \mathbb{N}\}$ is a context sensitive language. It ...
1
vote
0answers
156 views

grammar for binary number in base n

given a binary number b, is there any grammar that generates the languages of $1^x$ where $x$ is $b$ in base $n$ ($n \in \mathbb{N}$) e.g. if $b$ is 1100, the grammar should generates $11,1^{12},1^{36}...
0
votes
1answer
367 views

Complexity of Context Sensitive Languages

I was reading above complexity classes from Formal Languages and Automata book by Peter Linz. It gives following facts (in Theorem 5.2): Consider we have a CFG without null or unit productions. ...
-3
votes
2answers
91 views

Is the language $\{ w \in \{ a, b \}^{*} | |w|_{a} + |w|_{b} = 2^{n} \}$ context sensitive? [closed]

Is the language $\{ w \in \{ a, b \}^{*} : |w|_{a} + |w|_{b} = 2^{n} \}$ context sensitive ?
3
votes
1answer
2k views

PDA for { xy : |x| = |y|, x ≠ y} from its grammar, and intuition behind it

I know the grammar for the language $\{ xy : |x| = |y|, x ≠ y \}$ if $\Sigma=\{a,b\}$: $$ \begin{align*} &S→AB∣BA \\ &A→a∣aAa∣aAb∣bAa∣bAb \\ &B→b∣aBa∣aBb∣bBa∣bBb \end{align*} $$ I ...
4
votes
1answer
836 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 ...
-2
votes
1answer
162 views

Is the set of strings $0^{2k}10^{2k}10^{k}$ for $k \geq 0$ context-free?

I am able to solve $0^{k}10^{k}10^{j}$ where $ k < j$. and I was able to see that this is also a concatenation of two strings. How to do it for $0^{2k}10^{2k}10^{k}$ for $k \ge 0$?
6
votes
2answers
143 views

Context-sensitive grammars without permutation rules

Permutation rules are called those which are of the form $AB\Rightarrow^*BA$1. It is also proven that permutation rules expand context-free grammars and allow them produce non-context-free languages. ...
1
vote
2answers
1k views

Is {a^i b^j c^k | i≤j or (k=j≤i)} context sensitive?

$$L = \{a^i b^j c^k \mid i \le j \text{ or } (j \le i \text{ and } j = k)\}$$ I think the given language is CSL as i can break this language like this $$L = \{a^i b^j c^k \mid i \le j \text{ and } ...