The tag has no usage guidance.

learn more… | top users | synonyms

6
votes
1answer
113 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 ...
5
votes
0answers
70 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 ...
4
votes
1answer
47 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 ...
2
votes
1answer
45 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
65 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
66 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
99 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 ...
-2
votes
1answer
71 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
21 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
114 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
297 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
94 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
29 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
1
vote
1answer
83 views

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

what is language of repeat(L) = {ww | w ∊ L} ? 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 question .
3
votes
1answer
53 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
123 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 ...
15
votes
0answers
126 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
147 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
63 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
45 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 ...
4
votes
3answers
384 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-...
0
votes
2answers
104 views

Creating a grammar from the language

L = { a^n b^2n a^(n+2) : n>=1 } So I'm trying to construct the grammar and I'm getting stuck.Some example strings would be these (spaced out to help demonstrate the patterns): a bb aaa aa bbbb aaaa ...
1
vote
1answer
72 views

Context Free or Context Sensitive and why

I was given two languages $$L_1=\{0^k1^k0^m\mid k,m \in \mathbb{N}\text{ and }k < m\}$$ and $$L_2=\{a^mb^{m+1}\}$$ and I was asked to prove whether they are context free or sensitive. For $...
1
vote
0answers
48 views

Notable decidable operations on context-sensitive languages [closed]

It is not always so easy to determine which basic questions on languages are (un)decidable. Also due to Rice's theorem, many nontrivial questions on languages are undecidable. What are notable or ...
1
vote
3answers
221 views

Why isn't every monotonic grammar context sensitive free?

The question is really confusing me. I know every context sensitive grammar is monotonic but not vice versa. e.g. AB--->BA is monotonic but not context sensitive. Can someone explain to me in simple ...
1
vote
2answers
83 views

Grammar generating specific language

Construct a context-sensitive grammar that generates L: L = {a^n b^m c^k|k>n, k>m} I believe my productions should go along this lines: ...
6
votes
1answer
2k views

How to prove that context sensitive languages are closed under intersection and complement?

This is a question from the exam of our "Automata and Formal Languages" course. There is a question where asked to prove or disprove that any "relative complement" operation between two context ...
1
vote
1answer
151 views

Is this an example of a type-0 grammar that is not context-sensitive?

A type-0 grammar generates a recursively enumerable (RE) language. A RE language is also known as a semi-decidable language. A semi-decidable language is a particular kind of undecidable language: ...
6
votes
3answers
236 views

Context-sensitive grammar for the language of words concatenated with themselves

I'm looking for a context-sensitive grammar that describes the following language: $L = \{ ww \mid w ∈ \{a,b\}^{\ast}, |w| ≥ 1\}$ . I've got problems with the fact that no rules such as $X \to \...
0
votes
2answers
82 views

Can this grammar be simplified?

So, I have a book here, which has an example for context sensitive grammar, and the grammar is the famous $0^n1^n2^n$ , and it has: $$ \begin{align} S &\rightarrow 0BS2 \mid 012 \\ B0 &\...
4
votes
1answer
175 views

Type inference in compiler is context sensitive?

Have read in Compiler textbook that type inference is context sensitive. Can anyone explain why is it so? This means that we need context sensitive grammar in semantic analysis phase of a compiler ...
1
vote
1answer
192 views

Demonstrating that for every monotonic grammar there is an equivalent context-sensitive grammar

I'm trying to understand the equivalence in expressive power of formal grammars whose rules take the form: $$ \alpha \rightarrow \beta $$ where $ |\alpha| \leq |\beta| $ (called a monotonic grammar), ...
10
votes
4answers
1k views

Can someone give a simple but non-toy example of a context-sensitive grammar?

I'm trying to understand context-sensitive grammars. I understand why languages like $\{ww \mid w \in A^*\}$ $\{a^n b^n c^n \mid n\in\mathbb{N}\}$ are not context free, but what I'd ...
10
votes
1answer
657 views

Are all context-sensitive languages decidable?

I was going through the Wikipedia definition of context-sensitive language and I found this: Each category of languages is a proper subset of the category directly above it. Any automaton and any ...
2
votes
1answer
402 views

Which properties of context sensitive languages are decidable?

There are two context-sensitive languages, $L_1$ and $L_2$. Which of the following statements about them are decidable respectively undecidable? $L_1 = \emptyset$ $L_1 = \Sigma^*$ $L_1 \cap L_2 = \...