Talk:Kuroda normal form
![]() | This article is rated Start-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects: | |||||||||||||||||||||||||||||||||||||
|
Terminology / Meta-Variable Confusion
editThere is a problem, see: http://en.wikipedia.org/wiki/Talk:Chomsky_normal_form#Terminology_.2F_Meta-Variable_Confusion
A → B needed?
editIs 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)
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)
Origin of unrestricted version(s)
editMateescu 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)
14 years later...
editThe 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)