Is it also CSL?

Question

Is the following Language, L = {xxxx | x ∈ {0, 1}*} CSL or not? I saw a explanation say that it’s REC, but it didn’t say anything about it not being CSL and I used to think strings like {xx | x ∈ {0, 1}*} are CSL where the same strings keep repeating [like x here].

 

So is it CSL and please do also tell is there a rule to figure that out?

Comments

It should be such an obvious thing and is explained in Wikipedia itself. The point is if a language is CFL it must be CSL as well. 

“A formal language that can be described by a context-sensitive grammar, or, equivalently, by a noncontracting grammar or a linear bounded automaton, is called a context-sensitive language. Some textbooks actually define CSGs as non-contracting,[2][3][4][5] although this is not how Noam Chomsky defined them in 1959.[6][7] This choice of definition makes no difference in terms of the languages generated (i.e. the two definitions are weakly equivalent), but it does make a difference in terms of what grammars are structurally considered context-sensitive; the latter issue was analyzed by Chomsky in 1963.[“

---

@Sunnidhya Roy

Statements like “TM does not accept $\epsilon$” Or “CSG does not generate $\epsilon$” etc are WRONG statements.

The authors who write such statements, also write that “we ignore $\epsilon$ to make arguments easier as in practical applications, $\epsilon$ is not of much use”..

So, Statements like “TM does not accept $\epsilon$” Or “CSG does not generate $\epsilon$” etc come from Half Knowledge.

That’s why it is said that:

“Half knowledge is dangerous”.

---

Thank you @Deepak Poonia Sir, I had misconception regarding this as this is what I had learnt from the coaching but after @gatecse Sir mentioned the idea I thoroughly researched on this and identified where I was wrong. 

Gateoverflow website and Gateoverflow and Go classes test series has been an eye opener for me as it has helped me rectify so many misconceptions and also study Computer Science and Maths in their right essence.

Thank you to the entire community here at Gateoverflow.

 

Answer 1

Let $\Sigma$ be any input alphabet.

$L = \{ wwww | w \in \Sigma^* \}$ is CSL, But not CFL.

$L$ can be accepted by a $LBA$.

$LBA$ is a Turing Machine that uses only the (constant multiple of) tape space occupied by the input.

In simple words, $\color{red}{\text{$LBA$ is an Algorithm with $O(|w|)$ space complexity.}}$

Now, How much space do you need to recognize $x = wwww$ type of string??

Definitely, $O(|x|)$ space is all you need to recognize $x.$

So, $L$ is CSL. 

https://www.csa.iisc.ac.in/~deepakd/atc-2016/Seminar-LBA.pdf 

Answer 2

To summarize, the language L = {xxxx | x ∈ {0, 1}*} is not a context-sensitive language (CSL).

To determine whether a language is context-sensitive, you can try to come up with a linear-bounded automaton (LBA) that recognizes it, or you can try to prove that no such automaton exists. One way to do this is to use the pumping lemma for context-sensitive languages, which states that if a language is context-sensitive, then there exists a constant k such that any string in the language of length at least k can be pumped, or broken down into three substrings xyz such that xy^iz is also in the language for all positive integers i. If you can prove that a language does not satisfy the pumping lemma for context-sensitive languages, then you can conclude that it is not context-sensitive.

Another way to determine whether a language is context-sensitive is to try to come up with a context-sensitive grammar (CSG) that generates it. A CSG is a type of formal grammar that consists of a finite set of terminal symbols, a finite set of nonterminal symbols, a start symbol, and a set of productions. Each production has the form A -> B, where A is a nonterminal symbol and B is a string of terminal and nonterminal symbols. If you can come up with a CSG that generates a language, then you can conclude that the language is context-sensitive.

Comments

it is not regular language