Jump to content

Talk:Kuroda normal form

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia

Terminology / Meta-Variable Confusion

[edit]

There is a problem, see: http://en.wikipedia.org/wiki/Talk:Chomsky_normal_form#Terminology_.2F_Meta-Variable_Confusion

Janburse (talk) 12:31, 20 June 2011 (UTC)[reply]

A → B needed?

[edit]

Is A → B needed in the Kuroda normal form for context-sensitive languages? Mateescu and Salomaa don't give it... In the unrestricted case it's obviously redundant once you add A → ε, but I don't see right away how it's redundant in the context-sensitive case... JMP EAX (talk) 23:38, 16 August 2014 (UTC)[reply]

Since that's also absent in the one-sided/Penttonen version [in all presentations thereof], I guess the Kuroda is fine without it too, but I haven't yet figured out why. JMP EAX (talk) 00:13, 17 August 2014 (UTC)[reply]

Origin of unrestricted version(s)

[edit]

Mateescu and Salomaa (p. 190) appear to say they came up with it (actually only with one-side version for the unrestricted grammars, their Theorem 2.4), but it's not terribly clear. The unrestricted version is not in Kuroda's 1964 paper cited on this page (and the one-sided version for unrestricted is not in Penttonen). I suppose Meduna just thought it was better to generalize the form (without changing its name) and then presented the original(s) as a special case. JMP EAX (talk) 08:13, 17 August 2014 (UTC)[reply]

14 years later...

[edit]

The same spelling mistake in a book of Meduna [1]. I guess copyeditors don't really exist in academic publishing, do they... JMP EAX (talk) 15:55, 18 August 2014 (UTC)[reply]