Questions tagged [context-sensitive]

The tag has no usage guidance.

3
votes
1answer
45 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
81 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
48 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
127 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
52 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
56 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
30 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
22 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
39 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
63 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
84 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
235 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
104 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
330 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
132 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
871 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
476 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
892 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
110 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
231 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
115 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
328 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
87 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
521 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
150 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
99 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
676 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
330 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
591 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 ...
6
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
388 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
421 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
291 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
344 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
291 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
46 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
441 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
405 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 ...
1
vote
1answer
523 views

Does applying a homomorphism to the intersection of two CSLs yield RE languages?

For each language $L \in L(RE)$ there are a homomorphism $h$ and two context-free languages $L_1$ and $L_2$ such that $L = h(L_1 \cap L_2)$. I understand that this is because context-free languages ...
-1
votes
1answer
62 views

Create a grammer for [duplicate]

create a grammer for {a^nb^m, n>0, m=2^n+1} itS unrestricted grammer. I tried to but couldnt understand. if you know the answer please breif it. coz i m new in this subject
2
votes
1answer
214 views

What is language of repeat(L) = {ww | w ∊ L}? [closed]

What is language of repeat(L) = {ww | w ∊ L} ? My try: I know it {ww | w ∊ (a,b)*} is context sensitive language. Here , what is meant by "repeat(L)" ? Can you explain it ? It is not a homework ...
3
votes
1answer
56 views

Have non-regular language classes of infinite words been studied?

For regular languages we have $\omega$-regular languages which extend them to infinite words. Are there such extensions for CFG's, CSG's and recursively enumerable languages?
4
votes
2answers
178 views

From context-free to context-sensitive

I have a context-free language $L(G)$. I'm reading in a book that $L(G') = L(G) - \{{\epsilon}\}$ is context-sensitive but I cannot find a proof or confirmation of this fact; moreover, in other texts ...
19
votes
1answer
287 views

Machines for context-free languages which gain no extra power from nondeterminism

When considering machine models of computation, the Chomsky hierarchy is normally characterised by (in order), finite automata, push-down automata, linear bound automata and Turing Machines. For the ...
-1
votes
1answer
633 views

Context free grammar $\{a^n b^m c^k\; : \;k>m \; \; k>n\}$

Is this a CFL? $$\{a^n b^m c^k\; : \;k>m \; \; k>n\}$$ When on seeing $a$'s and $b$'s I push them onto stack and as I see $ c$ as input if $ TOS$ is $b$ ,I pop them ,again if $TOS$ is a,I pop ...
4
votes
1answer
113 views

Context-sensitive grammars for $a^ib^jc^{ij}$ and $a^ib^jc^{i^j}$

I would like to get some help for finding the context-sensitive grammar for the language: $$L_1=\{a^ib^jc^{ij} \mid i,j\geq 0\}.$$ To answer the question before it's written here, yes I've tried to ...
3
votes
0answers
110 views

Is there a grammar type for deterministic LBA?

Contextsensitive grammars define exactly the langauges acceptable by nondeterministic LBA. But how about deterministic LBA - is there a grammar type capturing exactly the languages acceptable by this ...
7
votes
3answers
2k views

How to generate a context sensitive grammar for www

I am trying to solve for my exam coming up and have no clue how to generate the grammar for Context sensitive languages for example how do i proceed on this kind of question. Give a context-...