5
$\begingroup$

I'm talking about Type-0 (Chomsky hierarchy) unrestricted grammar, where production rules of grammar are of the form $\alpha\rightarrow\beta$, where $\alpha,\beta\in N\cup\Sigma$.

I can not find any example of real unrestricted grammar which produces a non-context-sensitive language (of words). While there are examples of non-context-sensitive languages like here or here, there are not examples with proper grammars for them. Could somebody provide such example?

(Ideally if you would provide links to corresponding papers where such example(s) are described).

Note: I've tried to build unrestricted grammar for known universal Turing machines, as it was suggested in commentaries above. I've used JFLAP tool for this purposes. But obtained grammars appear to be extremely huge, incomprehensible and complex. If you would use same approach and give clear explanation of result, this would partially suit me. Thanks.

$\endgroup$
  • $\begingroup$ They definitely exist, since we know that unrestricted grammars are equivalent to Turing machines; moreover, the proof is constructive: given a Turing machine, it shows how to construct an equivalent grammar. $\endgroup$ – Yuval Filmus Jan 10 '17 at 20:38
  • 2
    $\begingroup$ A universal Turing machine will do. In this case the language will correspond to the halting problem, and so not computable, and in particular not context-sensitive. $\endgroup$ – Yuval Filmus Jan 10 '17 at 20:50
  • $\begingroup$ "but in this case we need example of Turing machine, which can not be described as push-down automata" -- even more; you need an example that's not expressible by LBAs. $\endgroup$ – Raphael Jan 11 '17 at 7:50
  • $\begingroup$ Building on Yuval's hint of picking an uncomputable problem: have a look at the PCP. (Note that we don't have to use an uncomputable problem; R \ CSL is not empty! But, before you ask, there is no grammar model for R.) $\endgroup$ – Raphael Jan 11 '17 at 7:52
  • $\begingroup$ @Raphael, you are saying: "convert any algorithm/TM for a non-context-sensitive language into a grammar" - I can convert, but I can not find such example yet. I have to check for all existent TM descriptions, that language produced by them isn't CSL. I will look on universal TM though $\endgroup$ – Andrey Lebedev Jan 11 '17 at 8:26
8
+50
$\begingroup$

For posterity.

Start with undecidable Post Correspondence Problem, or PCP:

Given two lists of words $(u_1,\dots,u_n)$ and $(v_1,\dots,v_n)$ does there exist a sequence of indices such that $u_{i_1}\dots u_{i_k} = v_{i_1}\dots v_{i_k}$?

The language will consist of PCP over $\{a,b\}$ that have a solution, coded as string $(u_1;v_1) \dots (u_n;v_n) $ with $u_i,v_i \in \{a,b\}^*$.

The grammar will generate a PCP instance, and non-deterministically an attempt for a solution. Then equality of the two strings is tested by deleting matching letters.

The equality check is more easily done when one of the strings is stored in reverse, so we will generate $u^R_{i_k} \dots u^R_{i_1} X v_{i_1}\dots v_{i_k}$.

Generate an instance of PCP.

  • $ I \to (W;W) I \mid (W;W) $ (add a pair of words)
  • $ W \to a W \mid b W \mid \varepsilon $ (generate a word)

Copy one of the pairs of PCP and move it to the pair of words around $X$ that should be equal.

  • $ D \tau \to \tau D$ for $\tau = a,b,(,),;$
  • $ D ( \to ( L $ (pair selected)
  • $ L ; \to ; R $
  • $ R ) \to ) $
  • $ L \sigma \to \sigma L_\sigma L $ for $\sigma = a,b$ (make a copy)
  • $ R \sigma \to \sigma R_\sigma R $ for $\sigma = a,b$

  • $ L_\sigma \tau = \tau L_\sigma $ for $\sigma = a,b$ and $\tau = a,b,(,),;$ (move right)

  • $ R_\sigma \tau = \tau R_\sigma $ for $\sigma = a,b$ and $\tau = a,b,(,),;$

  • $ L_\sigma X \to \sigma X$ (drop copy to the left of $X$, it will reverse)

  • $ R_\sigma X \to X \sigma$ (drop copy to the right of $X$)

Check equality

  • $ X \to Z $
  • $ \sigma Z \sigma \to Z$ for $\sigma = a,b$

Start. The $\#$ marks the end of the string, or rather the end of the solution that is generated. The last rule will delete it and at the same time test whether the solution has been completely removed by the earlier rules checking equality.

  • $ S \to C I X \#$
  • $ C \to C D \mid D $ for generating the solution, copy several word pairs

Done

  • $ ) Z \# \to )$

PS. Most constructions for a non-context-sensitive language use diagonalization on context-sensitive grammars to get a language that is still recursive. This one is not recursive, but recursively enumerable.

Indeed many rules are context-sensitive (or rather monotonic/non-contracting). But especially note the rules like $aZa\to Z$: they shorten the string. These are definitely type-0 and not monotonic, and they are essential. After the computation they delete the proposed solution of PCP. Like a scratch tape used by a Turing machine.

PS2. Although the intuitive meaning of each of the productions is explained above, it is not very simple to formally prove the grammar is correct. This is mostly due to the parallellism. There are many nonterminals moving around in the grammar at the same time independently (for instance, when a copy of a PCP pair $(u_i,v_i)$ is made all these letters move in a row to the right; also we can start looking for the next pair to copy even before the last one was finished). This makes it hard to formulate invariants. It takes some time to check that all nonterminals keep in a proper order, for instance. Fortunately none of the moving nonterminals can overtake one another.

For this reason analysing Turing Machines sometimes is less complicated. Only the reading/writing head is moving around.

Example (added by Andremoniy)

Consider simplest case: $(a;a)$. For this string derivation sequence will be:

$S\Rightarrow CIX\Rightarrow D(W;W)X\Rightarrow C(a;a)X\Rightarrow D(a;a)X\Rightarrow (La;a)X\Rightarrow (aL_aL;a)X\Rightarrow (aL_a;Ra)X\Rightarrow (a;L_aRa)X\Rightarrow (a;L_a aR_aR)X\Rightarrow (a;aL_aR_aR)X\Rightarrow (a;aL_aR_a)X\Rightarrow (a;aL_a)R_aX\Rightarrow (a;a)L_aR_aX\Rightarrow (a;a)L_aXa\Rightarrow (a;a)aXa\Rightarrow (a;a)aZa\Rightarrow (a;a)Z\Rightarrow (a;a)$

$\endgroup$
  • $\begingroup$ Wow. Looks like you did a great job. In any case thank you and +1. As soon as I sober up (most possibly tomorrow) I will try to understand this and reward you with my bounty $\endgroup$ – Andrey Lebedev Jan 13 '17 at 21:40
  • $\begingroup$ Dear @HendrikJan, could you clarify 2 things: 1) what is '#' - is it empty symbol or symbol it self (more generally, could you formally describe alphabet for this particular grammar) and 2) this grammar looks like context-sensitive (as all rules of the form Ab -> bA could be expanded to the proper form of CSG). Am I wrong? $\endgroup$ – Andrey Lebedev Jan 13 '17 at 21:46
  • 1
    $\begingroup$ Don't hand out the bounty too soon. You will attract other people that perhaps have more elegant solutions! $\endgroup$ – Hendrik Jan Jan 14 '17 at 0:05
  • 1
    $\begingroup$ The $L_\sigma$ and $R_\sigma$ move the letter $\sigma$ to its proper place (where $\sigma$ can be either $a$ or $b$). I had a $M_\sigma$ is a previous edition. I will correct (there is an $X$ missing there too). $\endgroup$ – Hendrik Jan Jan 14 '17 at 21:09
  • 1
    $\begingroup$ The 'duplicator' D should skip over various pairs $(u_i,v_i)$ until it chooses one. Nondeterministically. At that moment L and R take over to copy the left and right parts $u$ and $v$ which are then moved and concatenated to the solution strings. $\endgroup$ – Hendrik Jan Jan 15 '17 at 20:48

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.