Skip to main content
27 votes
Accepted

Number of words of length n in a context-free language

Every context-free language has either polynomial growth or exponential growth. In the notation of the question poser: Either there is a polynomial $p$ so that $w_n\le p(n)$ for all $n$ Or there ...
Gamow's user avatar
  • 5,772
25 votes

Theoretical Computer Science vs other Sciences?

As a theoretical computer scientist I am proud of the following achievements of the field. Logicians figured out that all logical connectives can be build from a single one, paving the road for ...
Andrej Bauer's user avatar
  • 29.2k
18 votes

Irreducible languages

There is the notion of primality of a language. It asks whether L can be written as $L_1 \cdot L_2$ where neither factor contains the empty word. A language is prime if it cannot be written in this ...
Thomas S's user avatar
  • 1,417
18 votes

Theoretical Computer Science vs other Sciences?

As a TCS researcher, I understand the feeling and feel it too sometimes. I think it is healthy to be able to appreciate the wonder that other sciences have to offer. We must also keep in mind that it ...
Denis's user avatar
  • 8,903
16 votes
Accepted

What is the name of a function $f$ such that $f(x,y) \in L \iff x\in L \wedge y \in L$?

They are typically called AND-functions. (I'm not joking.) Indeed, this concept has been considered before, and that's what people call them. See, for example, the book by Kobler, Schoning, and Toran ...
Joshua Grochow's user avatar
14 votes

Irreducible languages

Another paper to look at: Kai Salomaa, "Language Decompositions, Primality, and Trajectory-Based Operations", 2008.
Jeffrey Shallit's user avatar
13 votes
Accepted

Can we approximate the number of words accepted by an NFA?

There exists a FPRAS (Fully Polynomial Randomized Approximation Scheme) for the problem of counting the words of length $n$ accepted by a NFA in the general case (without restricting to the acyclic ...
ricardorr's user avatar
  • 561
13 votes

On the realisation of monoids as syntactic monoids of languages

The terminology rigid seems to be relatively new compared to the term disjunctive used in the late 70's (and probably before, I didn't check for earlier references). A subset $P$ of a monoid $M$ is ...
J.-E. Pin's user avatar
  • 4,841
13 votes
Accepted

Is the Set of all Primitive Words a Prime Language?

The answer is yes. Suppose we have a factorization $Q = A\cdot B$. One easy observation is that $A$ and $B$ must be disjoint (since for $w\in A\cap B$ we get $w^2\in Q$). In particular, only one of $...
Klaus Draeger's user avatar
13 votes
Accepted

Ambiguity of regular expressions

Yes, every regular expression can be converted into an unambiguous one by converting to a DFA and then to a regular expression. And no, there aren't any inherently ambiguous regular languages in the ...
Hermann Gruber's user avatar
13 votes

Determinising unambiguous automata without exponential blowup

No, the exponential lower bound for determinization holds already for unambiguous NFAs. This is obtained as follows: Consider the alphabet $\{a,b\}$, and the language: $$L_k=\{w\in \{a,b\}^*:\text{the ...
Shaull's user avatar
  • 5,656
12 votes
Accepted

On the realisation of monoids as syntactic monoids of languages

It seems there is a paper answering this exact question, and even in the more general case of $\omega$-regular languages, but I cannot find an open-access version. If somebody finds a link without ...
Denis's user avatar
  • 8,903
12 votes
Accepted

What is the conjectured relationship between P (PTime) and Type 1 (context-sensitive) languages?

If $\mathrm{P\subseteq CSL}$, then $\mathrm{P\subseteq DSPACE}(n^2)$. By a padding argument, this implies $$\mathrm{DTIME}(t(n))\subseteq\mathrm{DSPACE}\bigl(t(n)^\epsilon\bigr)$$ for every ...
Emil Jeřábek's user avatar
12 votes

NP-complete decision problems on deterministic automata

The decision version of the DFA identification problem (find a possibly non-unique smallest DFA that is consistent with a set of given labeled examples) is NP-complete: Input: Integer $k$ and sets $...
Marzio De Biasi's user avatar
11 votes

On the realisation of monoids as syntactic monoids of languages

In a more elementary way than Denis's answer, the following is extracted from Pippenger's "Theories of Computability", p.87, and immediate to check. Definition: Let $M$ be a monoid, and $Y \subseteq ...
Michaël Cadilhac's user avatar
11 votes
Accepted

What is the motivation behind defining Deterministic Looping Automata?

In a looping automaton, the transition function is not assumed to be total. That is, for a state $q$ and a letter $\sigma$, it could be the case that $\delta(q,\sigma)$ is undefined. Intuitively, this ...
Shaull's user avatar
  • 5,656
11 votes
Accepted

Size of complement of context-free language

From the proof that determining if a CFL ${L}$ = $\Sigma^*$ is undecidable, the set of strings $ID_0\#ID_1^R\#ID_2\#ID_3^R\#\ldots\#ID_t$ where $ID_0,ID_1,\ldots,ID_t$ is a list of the configurations ...
Lance Fortnow's user avatar
11 votes
Accepted

Is the complement of { www | … } context-free?

Still CFL I believe, with an adaptation of the classical proof. Here's a sketch. Consider $L = \{xyz : |x|=|y|=|z| \land (x \neq y \lor y \neq z)\}$, which is the complement of $\{www\}$, with the ...
Michaël Cadilhac's user avatar
11 votes
Accepted

Example of an context-sensitive language with a specific number of words of length $n$

The language $$L=\bigcup_{n\in\mathbb N}\{0,1\}^{\lfloor n^\delta\rfloor}0^{n-\lfloor n^\delta\rfloor}$$ is computable in $\mathrm L\subseteq\mathrm{NSPACE}(n)=\mathrm{CSL}$, and it has $s_L(n)=2^{\...
Emil Jeřábek's user avatar
11 votes

Theoretical Computer Science vs other Sciences?

I run a small software business producing XML processing tools, so I'm very much a practical engineer rather than a theoretician. It's 50 years since I did my CS degree. And you know, I'm constantly ...
Michael Kay's user avatar
11 votes

List of nice non-context-free languages

If I had to summarize the capabilities/limitations of CF languages I would say: they can pair "things" but two distinct pairings cannot overlap they can "count" but only linearly (...
Marzio De Biasi's user avatar
10 votes
Accepted

Known and described subclasses of Context-Free Grammars class

Density might be interesting concept for you. The density function is defined as $$\delta_L(n) := |L\cap \Sigma^n|,$$ where $\Sigma^n$ denotes the set of all strings of length $n$ over $\Sigma$. ...
Peter Leupold's user avatar
10 votes
Accepted

Is equivalence of unambiguous context-free languages decidable?

This is currently an open problem. As correctly pointed out, if it is decidable, then one expects the proof to be hard since it generalises the famous DPDA equivalence problem. On the other hand, the ...
Lorenzo's user avatar
  • 118
10 votes

Base-k representations of the co-domain of a polynomial - is it context-free?

Of course $k \geq 2$ here. There once was a manuscript by Horváth that claimed to solve the problem, but it was unclear in several places and to my knowledge was never published. As far as I know, ...
Jeffrey Shallit's user avatar
10 votes

Is the complement of { www | … } context-free?

Here is the way I think about solving this problem, with a PDA. In my opinion, it's intuitively clearer. A word $x$ is not of the form $www$ iff either (i) $|x| \not\equiv 0$ (mod 3), which is easy ...
Jeffrey Shallit's user avatar
10 votes

Theoretical Computer Science vs other Sciences?

My impression from your comments is that perhaps you have just not seen enough theoretical CS to get to some of the kind of content you are excited about in, say, physics. I'll also point out that you ...
Joshua Grochow's user avatar
9 votes

Real computers have only a finite number of states, so what is the relevance of Turing machines to real computers?

A formalism is useful or not, based on what people want to use the formalism to model and understand. The Turing machine is a formalism that is useful for understanding programs. Programs are worth ...
Eric Allender's user avatar
9 votes

Counting words accepted by a regular grammar

I think this is a hard counting problem, see this paper: Counting the size of regular sequences of given length is #P-complete: S. Kannan, Z. Sweedyk, and S. R. Mahaney. Counting and random generation ...
Miklós István's user avatar
9 votes

Deciding whether a unary context-sensitive language is regular

Alas, your problem is undecidable. The approach I stumbled upon (which might be overwrought, so anyone who has a more expedient approach should step up!) first uses a diagonal argument to demonstrate ...
gdmclellan's user avatar
9 votes
Accepted

Mistake in Wikipedia CSG example?

If I am not mistaken, a simpler CS grammar is possible. Here it is: $S \rightarrow ABSc$ $S \rightarrow Abc$ $BA \rightarrow XA$ $XA \rightarrow XY$ $XY \rightarrow AY$ $AY \rightarrow AB$ $A \...
Jeffrey Shallit's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible