Matches in DBpedia 2015-10 for { <http://dbpedia.org/resource/Kuroda_normal_form> ?p ?o }
Showing triples 1 to 52 of
52
with 100 triples per page.
- Kuroda_normal_form abstract "In formal language theory, a grammar is in Kuroda normal form if all production rules are of the form:AB → CD orA → BC orA → B orA → awhere A, B, C and D are nonterminal symbols and a is a terminal symbol. Some sources omit the A → B pattern.It is named after Sige-Yuki Kuroda, who originally called it a linear bounded grammar—a terminology that was also used by a few other authors thereafter.Every grammar in Kuroda normal form is noncontracting, and therefore, generates a context-sensitive language. Conversely, every context-sensitive language which does not generate the empty string can be generated by a grammar in Kuroda normal form.A straightforward technique attributed to György Révész transforms a grammar in Kuroda's form to Chomsky's CSG: AB → CD is replaced by four context-sensitive rules AB → AZ, AZ → WZ, WZ → WD and WD → CD. This technique also proves that every noncontracting grammar is context-sensitive.There is a similar normal form for unrestricted grammars as well, which at least some authors call "Kuroda normal form" too:AB → CD orA → BC orA → a orA → εwhere ε is the empty string. Every unrestricted grammar is [weakly] equivalent to one using only productions of this form.If the rule AB → CD is eliminated from the above, then one obtains context-free languages. The Penttonen normal form (for unrestricted grammars) is a special case where A = C in the first rule above. For context-sensitive grammars, the Penttonen normal form, also called the one-sided normal form (following Penttonen's own terminology) is just:AB → AD orA → BC orA → aAs the name suggests, for every context-sensitive grammar, there exists a [weakly] equivalent one-sided/Penttonen normal form.".
- Kuroda_normal_form wikiPageExternalLink pdf?md5=0a10da0e20ccd77c5d61461764f42e5f&pid=1-s2.0-S0019995864901202-main.pdf.
- Kuroda_normal_form wikiPageExternalLink pdf?md5=d7c0b3b4f8d19a9ab1d49670a53d4732&pid=1-s2.0-S0019995874910493-main.pdf.
- Kuroda_normal_form wikiPageID "1102836".
- Kuroda_normal_form wikiPageLength "4959".
- Kuroda_normal_form wikiPageOutDegree "13".
- Kuroda_normal_form wikiPageRevisionID "622589114".
- Kuroda_normal_form wikiPageWikiLink Backus-Naur_form.
- Kuroda_normal_form wikiPageWikiLink Backus–Naur_Form.
- Kuroda_normal_form wikiPageWikiLink Category:Formal_languages.
- Kuroda_normal_form wikiPageWikiLink Chomsky_normal_form.
- Kuroda_normal_form wikiPageWikiLink Context-sensitive_language.
- Kuroda_normal_form wikiPageWikiLink Empty_string.
- Kuroda_normal_form wikiPageWikiLink Formal_grammar.
- Kuroda_normal_form wikiPageWikiLink Formal_language.
- Kuroda_normal_form wikiPageWikiLink Formal_language_theory.
- Kuroda_normal_form wikiPageWikiLink Greibach_normal_form.
- Kuroda_normal_form wikiPageWikiLink Noncontracting_grammar.
- Kuroda_normal_form wikiPageWikiLink Nonterminal.
- Kuroda_normal_form wikiPageWikiLink S.-Y._Kuroda.
- Kuroda_normal_form wikiPageWikiLink Sige-Yuki_Kuroda.
- Kuroda_normal_form wikiPageWikiLink Terminal_and_nonterminal_symbols.
- Kuroda_normal_form wikiPageWikiLink Terminal_symbol.
- Kuroda_normal_form wikiPageWikiLink Unrestricted_grammar.
- Kuroda_normal_form wikiPageWikiLinkText "Kuroda normal form".
- Kuroda_normal_form hasPhotoCollection Kuroda_normal_form.
- Kuroda_normal_form wikiPageUsesTemplate Template:Cite_journal.
- Kuroda_normal_form wikiPageUsesTemplate Template:Doi.
- Kuroda_normal_form wikiPageUsesTemplate Template:Formal_languages_and_grammars.
- Kuroda_normal_form wikiPageUsesTemplate Template:Reflist.
- Kuroda_normal_form subject Category:Formal_languages.
- Kuroda_normal_form hypernym Symbols.
- Kuroda_normal_form type Country.
- Kuroda_normal_form type Language.
- Kuroda_normal_form type Combinatoric.
- Kuroda_normal_form type Language.
- Kuroda_normal_form type Method.
- Kuroda_normal_form comment "In formal language theory, a grammar is in Kuroda normal form if all production rules are of the form:AB → CD orA → BC orA → B orA → awhere A, B, C and D are nonterminal symbols and a is a terminal symbol.".
- Kuroda_normal_form label "Kuroda normal form".
- Kuroda_normal_form sameAs Kurodin_normalni_oblik.
- Kuroda_normal_form sameAs Kuroda-Normalform.
- Kuroda_normal_form sameAs Kurodin_normalni_oblik.
- Kuroda_normal_form sameAs Forma_normale_di_Kuroda.
- Kuroda_normal_form sameAs 黒田標準形.
- Kuroda_normal_form sameAs Postać_normalna_Kurody.
- Kuroda_normal_form sameAs Forma_normal_de_Kuroda.
- Kuroda_normal_form sameAs m.0465st.
- Kuroda_normal_form sameAs Q1452617.
- Kuroda_normal_form sameAs Q1452617.
- Kuroda_normal_form sameAs 黑田范式.
- Kuroda_normal_form wasDerivedFrom Kuroda_normal_form?oldid=622589114.
- Kuroda_normal_form isPrimaryTopicOf Kuroda_normal_form.