18
$\begingroup$

It is a well-known result that the question

Does a context-free grammar generate a regular language?

is undecidable. However, it becomes decidable on a unary alphabet, simply because in this case, the classes of context-free and regular languages coincide.

My question is to know what happens for unary context-sensitive languages.

Is it decidable to know whether a given context-sensitive grammar on a unary alphabet generates a regular language.

If the answer is positive, an estimation of the complexity would be welcome.

$\endgroup$
9
$\begingroup$

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 that there is a unary CSL $X$ which isn't regular (in contrast to the positive result for unary CFLs), and then reduces from the halting problem for Turing machines by, given a TM $M$, constructing a CSG $G$ which simulates $M$ on a length of tape shorter than the parse string $w$, recognising $X$ if $M$ halts without overstepping its bounds and failing to parse otherwise, so that $G$ successfully parses all $w \in X$ that are sufficiently long iff $M$ halts (so that $L(G)$ differs from $X$ on only finitely many strings and therefore cannot be regular), otherwise $G$ recognizes the empty language (which is clearly regular).

Key to this approach is the observation that CSGs are not merely concerned with grammatical matters such as phrase structure -- indeed, CSG derivation sequences can carry out arbitrary nondeterministic space-bounded computation (indeed there are $\mathbf{PSPACE}$-complete CSLs) before ever getting to the business of aligning with the parse string. This is most easily observed via standard conversions between CSGs and monotonic grammars (which continues to work when restricted to unary alphabets), and the use of simple monotonic productions to simulate Turing machine transitions on derivation strings which represent stages in a computation history. Throughout this answer I'm going to assume the reader can intuit most of the details when a CSG is required to simulate a given computation. (I assume the asker is comfortable with all of this, but I'm going over it for completeness. Nevertheless, feel free to request clarification in the comments.)


Firstly, we need our non-regular unary CSG. (EDIT: so, this was overkill -- non-regular unary CSLs can easily be exhibited e.g. via the pumping lemma on any language which exhibits the most basic of non-regularity. See the comments for examples. In hindsight, using a diagonal argument was like bringing a nuclear warhead to a knife fight. Peruse this construction if you're curious, otherwise skip to the reduction.)

Let $D_1, D_2, ... $ be an enumeration of DFAs over alphabet $\{1\}$, such that the number of states in $D_i$ increases in $i$. We describe a CSG $G_X$ in terms of its behaviour whilst parsing string $1^n \in \{1\}^*$:

  1. Nondeterministically generate a string of $n$ "blank" non-terminals, which we think of as the "tape". One of the blank non-terminals should be a separate "blank + read-write head + start state" non-terminal. If the parse string isn't $1^n$ then this derivation will end up failing. We describe the rest of the process in terms of the deterministic computation simulated by the only possible derivation.
  2. Print on the tape an encoding of $D_i$ followed by the number $i$ in binary, where $i = n - c$ and $c$ is chosen so that we always have enough space on our tape to do what we need to. (This is possible since the space required to encode both $D_i$ and $i$ grows logarithmically in $i$.)
  3. Evaluate $D_i$ on input $1^i$. This doesn't require a representing $D_i$'s tape -- you can just store a single state, which you change according to the transitions of $D_i$ as you decrement $i$.
  4. If $D_i$ rejects $1^i$, overwrite the entire tape with non-terminals which produce $1$. Otherwise fail.

We take $X = L(G_X)$. Clearly $X \ne L(D_i)$ for any $i$, since $1^{i+c} \in X \Leftrightarrow 1^{i+c} \notin L(D_i)$.


The next step is to design a reduction from the halting problem to the asker's problem. (If you skipped the above section, let $X$ be an arbitrary non-regular unary CSL generated by CSG $G_X$.)

Let $M$ be an arbitrary TM. We convert $M$ into a CSG $G$ which behaves as follows on parse string $1^n$:

  1. Generate $n-2$ blank non-terminals, the leftmost one being the separate blank + read-write head non-terminal, and also generate a "boundary" non-terminal on each side. Again, if we generate the wrong number of non-terminals then we fail.
  2. Simulate $M$ in the space between the boundary non-terminals. If $M$ ever shifts onto one of the boundary states, we terminate the simulation and assume that $M$ never halts.
  3. If $M$ halts, behave like $G_X$. If we had to terminate the simulation, then fail.

Note that if $M$ manages to run forever within the boundaries then $G$ can never generate a parse string and so will fail. If $M$ halts, then there is some amount of space $n$ which suffices to contain $M$'s entire computation, hence $G$ parses $1^m$ whenever $m \ge n+2$ and $1^m \in X$, and hence $X$ is the union of $L(G)$ and a finite language, whence $L(G)$ is not regular. On the other hand, if $M$ never halts, then $L(G) = \varnothing$ is clearly regular.

An algorithm for deciding whether $L(G)$ is regular or not would determine whether or not $M$ halts on a blank tape, which is undecidable. It follows that the asker's problem is undecidable.

$\endgroup$
  • 2
    $\begingroup$ For the first part of your answer, $\{a^{n^2} \mid n \geqslant 0\}$ and $\{a^p \mid \text{$p$ is prime}\}$ are examples of unary context-sensitive nonregular languages. $\endgroup$ – J.-E. Pin Jun 21 '16 at 6:46
  • $\begingroup$ Heh, overwrought indeed, it probably should've occurred to me that a diagonal argument would be gross overkill. I guess I'll edit a note into the answer. Hope the second part was helpful nevertheless. $\endgroup$ – gdmclellan Jun 21 '16 at 7:07
  • $\begingroup$ @J.-E.Pin: I didn't think about it too much, is it easy to construct an unary context sensitive grammar for $\{a^p \mid p \mbox{ is prime}\}$ ? $\endgroup$ – Marzio De Biasi Jun 21 '16 at 8:54
  • $\begingroup$ @marzio-de-biasi I have to confess I didn't check myself but relied on this answer $\endgroup$ – J.-E. Pin Jun 21 '16 at 9:18
  • $\begingroup$ @MarzioDeBiasi Very easy. When determining whether a language is context-sensitive, the usual process is something like 1. nondeterministically guess the parse string; 2. carry out some space-bounded computation to determine whether the parse string satisfies some predicate; and 3. generate the string iff said predicate is found to be satisfied. Space can be a bit of an issue (the space bound is given by the length of the parse string, because you can't contract a derived string using context-sensitive productions), but in the unary case you have exponential space to work with. $\endgroup$ – gdmclellan Jun 21 '16 at 10:39
6
$\begingroup$

This is essentially the same answer as above, but since a "more expedient" answer is sought, I'm mentioning this: (Also, this is my first post here, so forgive me if I'm posting a triviality!)

Observe that emptiness is undecidable for unary context-sensitive languages. Fix a context-sensitive, but non-regular language $N\subseteq a^*$. Given an LBA for $L\subseteq a^*$, one can easily construct an LBA for $L'=\{ a^n \mid \text{$a^n\in N$ and $\exists m\le n\colon a^m \in L$}\}$. Then clearly $L'$ is regular if and only if $L$ is empty.

Update: Of course, the same argument shows that undecidability already holds for deterministic logarithmic space.

$\endgroup$
  • $\begingroup$ "emptiness is undecidable for unary context-sensitive languages": is it a well-known fact? Would you have a reference? $\endgroup$ – J.-E. Pin Jun 27 '16 at 15:37
  • 1
    $\begingroup$ Given a contex-sensitive language $L\subseteq\Sigma^*$, take the morphism $h\colon\Sigma^*\to\{a\}^*$ that maps every letter to $a$. Then $h(L)$ is empty if and only if $L$ is empty. For deterministic logspace, given a TM $T$, one can construct a det. logspace TM for the the set of all $a^{2^n}$ such that $T$ has a halting computation of length $n$. $\endgroup$ – Georg Zetzsche Jun 27 '16 at 16:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.