Podcast #128: We chat with Kent C Dodds about why he loves React and discuss what life was like in the dark days before Git. Listen now.

Questions tagged [context-sensitive]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
-3
votes
1answer
37 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
0answers
18 views

How many internal nodes does this derivation tree have?

Given a CFG in CNF, how many internal nodes (i.e., nodes that are not leaves) does the derivation tree of the string "Halloween" have?
2
votes
1answer
36 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
23 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
42 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
42 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
45 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 ...
0
votes
0answers
18 views

Why are CFL not closed under set difference, and complementation? [duplicate]

I was wondering why CFL are not closed under set difference, and complementation can anyone explain? I tried searching, but no luck.
4
votes
1answer
123 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
19 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, ...
3
votes
1answer
62 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
102 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
63 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
163 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
54 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
60 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
34 views

What is abstract machine for parallel multiple context free grammar (PMCFG)?

It is said, that PMCFG (Parallel multiple context free grammar) http://www.aclweb.org/anthology/P93-1018 is mildly context-sensitive grammar. My question is - what abstract machine can be used for ...
0
votes
0answers
37 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
47 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
80 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
85 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
34 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
236 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
107 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 ...
9
votes
4answers
362 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
142 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 ...
1
vote
1answer
968 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
528 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
1k 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
119 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, ...
7
votes
1answer
233 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
132 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
340 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
88 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
1k 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
591 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
154 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$?
5
votes
2answers
104 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
713 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 } ...
8
votes
1answer
346 views

Can there be a context-sensitive pumping lemma?

A "pumping" property (words of a certain length imply the existence of loops in the language-defining mechanism) are known to exist for regular and context-free languages and a few more (usually used ...
6
votes
1answer
646 views

What would a formal grammar for a binary file format look like?

Binary structures often feature length specifiers; the parser is supposed to read them and then consume the specified amount of symbols. Because of this, the grammar is context-sensitive. What would ...
7
votes
1answer
2k views

Is there an example of a recursive language which is not context sensitive?

I have been looking for a prototypical language for recursive languages (decidible) which is no context sensitive without success. For instance $a^*$ is prototypical of regular languages, $a^nb^n$ for ...
5
votes
1answer
425 views

Examples of context sensitive syntactic constructs (statements)

So, I am implementing a context sensitive syntactic analyzator. It's kind of an experimantal thing and one of the things I need are usable syntactical contructs to test it on. For example, the ...
3
votes
1answer
450 views

Membership problem for context sensitive languages PSPACE-complete

I have read that the membership problem for CSL is PSPACE-complete but I couldn't find the proof anywhere. So I tried it myself. Let's mark the membership problem for CSL as MEM. First I have to ...
1
vote
1answer
302 views

context sensitive language finite or infinite

let L be a CSL. (my understanding/ memory/ expectation is) the problem is L finite or infinite? is undecidable. where was this 1st proved/ published? are there any cases in the literature of ...
0
votes
2answers
379 views

Grammar for square numbers in unary

I have to write a grammar for the following language: $$\{1^{n^2} \mid n\geq 1 \}$$ I am having trouble figuring out the production rules. I was thinking of using the fact that $n^2$ can be written as ...
-1
votes
1answer
297 views

Context sensitive grammar for an odd number of copies of the same word

Let $L = \{ w^m \mid m = 2k +1, k \ge 1 \}$. Please give some idea to write a Context sensitive grammar for $L$. Will it be like $L' = \{www \mid w \in \{a, b\}^*$? Then for each $w$ we have to ...
4
votes
1answer
47 views

How to make sense of this context-sensitive production in a textbook? (a typo perhaps?)

In Chapter 1 of Kenneth Slonneger and Barry L. Kurtz's Formal Syntax and Semantics of Programming Languages: A Laboratory Based Approach, an example of its production is given to illustrate the nature ...
1
vote
2answers
470 views

Ambiguity vs. context-sensitivity

It is said that attributes supply some semantic information to the grammar. Meantime, the same attributes let you to resolve ambiguities. Text books agree that it is worth haveing a CF grammar which ...
7
votes
1answer
421 views

Class of the language only containing the empty string?

$L = \left \{ \epsilon \right \}$ Clearly this language is finite so this must be a regular language. Now since every regular language is Context Sensitive, $L$ is a CSL. We can define the grammar ...