Talk:Unrestricted grammar

Untitled

I believe the following is incorrect. Can someone confirm?

$P$ is a set of production rules of the form $\alpha \to \beta$ where $\alpha$ and $\beta$ are in $N\cup \Sigma$

I say this because in this snippet:

If $\beta$ appears at some position on the second tape, replace $\beta$ by $\gamma$ at that point, possibly shifting the symbols on the tape left or right depending on the relative lengths of $\beta$ and $\gamma$ (e.g. if $\beta$ is longer than $\gamma$, shift the tape symbols left).

... it looks like $\alpha$ and $\beta$ are sequences, so not in $N\cup \Sigma$, but in the set of all finite sequences using letters from the alphabet $N\cup \Sigma$ (I'm not sure the best way to notate this, maybe something from Sequence_space)

Pchiusano 02:49, 26 July 2006 (UTC)

Yes, you're right; someone must have written without really thinking. Ruakh 13:10, 26 July 2006 (UTC)

In the definition, I believe all the sets should be finite. I will change this soon unless I hear back otherwise. 129.15.139.171 (talk) 14:56, 27 March 2012 (UTC)

Terminals only on left hand side not always allowed

@Jochen Burghardt:

1. Could you please provide the section number for this cite? I can only access editions 2 and 3.
2. Chomsky's Axiom 2 ("A∈V_N if and only if there are φ,ψ,ω such that φAψ → φωψ"[1]) excludes, among others, production rules of the form a→ω, where a is a non-terminal.

Paradoctor (talk) 00:42, 13 September 2018 (UTC)

@Paradoctor: (User name inferred from history page)

1. In the 1979 edition, chapter 9 (p.217-233) is named "The Chomsky hierarchy", its section 9.2 (p.220-223) is named "Unrestricted grammars", its section 9.3 (p.223-226) "Context-sensitive languages". It seems that in the later editions, these sections were omitted. The initial paragraph of section 9.2 reads:

   The largest family of grammars in the Chomsky hierarchy permits productions of the form $\alpha \to \beta$, where $\alpha$ and $\beta$ are arbitrary strings of grammar symbols, with $\alpha \neq \varepsilon$. These grammars are known as semi-Thue, type 0, phrase structure or unrestricted grammars. We shall continue to use the 4-tuple notation $G=(V,T,P,S)$ for unrestricted grammars. We say $\gamma \alpha \delta \Rightarrow \gamma \beta \delta$ whenever $\alpha \to \beta$ is a production. As before, ${\stackrel {*}{\Rightarrow }}$ stands for the reflexive and transitive closure of the relation $\Rightarrow$ : $L(G)=\{w\mid w{\mbox{ is in }}T^{*}{\mbox{ and }}S{\stackrel {*}{\Rightarrow }}w\}$, exactly as for context-free grammars.

   After that, an example grammar for $\{a^{i}\mid i{\mbox{ is a power of 2 }}\}$ follows; it actually uses only productions with nonterminals in the lhs. Then they construct in Thm. 9.3 a (nondeterministic) Turing machine for every unrestricted grammar, and in Thm. 9.4 an unrestricted grammar for every acceptor Turing machine. Again, the latter grammar has a nonterminal in each production's lhs. However, Thm 9.3 works also if no nonterminal is in a production's lhs. So, by applying Thm 9.3 and then 9.4, every unrestricted grammar can be transformed into a version having a nonterminal in each lhs.
2. Maybe, Hopcroft/Ullman's definition deviates from Chomsky's original version in his 1959 paper cited by you. However, in that paper "$\to$" (also called "can be rewritten as") corresponds to "$\Rightarrow$" in Hopcroft/Ullman's book, while the finite pair set (also called "rules") from Ax.4 corresponds to H/U's $\to$. So it seems to me that in Ax.2 the "if" direction requires to stop further rewriting once all nonterminals have disappeared from the string (i.e. as long as there are nonterminals present in the string, terminal-only-lhs productions may well be applied to it). The "only if" direction seems to require that an applicable rule exists for every derivable string containing a nonterminal; e.g. the context-free grammar consisting of the single rule $S\to A$ wouldn't be admitted by that, whereas today we'd consider it as valid, and producing the empty language. This indicates to me that some details of Chomsky's initial definition are no longer in force today. Another example is $S\to S$, contradicting Ax.1. - Jochen Burghardt (talk) 09:48, 13 September 2018 (UTC)

(No need to ping, I'm watching) Sorry for the missing sig. Thanks for the quote. "Tbd"? Paradoctor (talk) 09:58, 13 September 2018 (UTC)

You need one non-terminal on the left hand side, otherwise you get pathological cases where the union of two grammars produces more than the union of their languages. E.g. G1=(S1->a,b->c), G2=(S2->b), G = G1 + G2 = (S->S1,S->S2,S1->a,S2->b,b->c). Here we have L1={a}, L2={b}, but L={a,b,c}. The German Wikipedia got that right, see: https://de.wikipedia.org/w/index.php?title=Chomsky-Hierarchie&oldid=229255677#Typ-0-Grammatik_(allgemeine_Chomsky-Grammatik_oder_Phrasenstrukturgrammatik) Andreasabel (talk) 16:28, 22 February 2023 (UTC)

I agree that the usual construction of a grammar for the union language wouldn't work any longer. However, other union constructions would still work, e.g. convert G1 and G2 to Turing machines, convert them back to grammars (with a nonterminal in every LHS), then apply your construction to them. - Jochen Burghardt (talk) 18:40, 22 February 2023 (UTC)