Analogical Conception of Chomsky Normal Form and Greibach Normal Form for Linear, Monadic Context-Free Tree Grammars
Summary :
This paper presents the analogical conception of Chomsky normal form and Greibach normal form for linear, monadic context-free tree grammars (LM-CFTGs). LM-CFTGs generate the same class of languages as four well-known mildly context-sensitive grammars. It will be shown that any LM-CFTG can be transformed into equivalent ones in both normal forms. As Chomsky normal form and Greibach normal form for context-free grammars (CFGs) play a very important role in the study of formal properties of CFGs, it is expected that the Chomsky-like normal form and the Greibach-like normal form for LM-CFTGs will provide deeper analyses of the class of languages generated by mildly context-sensitive grammars.
- Publication
- IEICE TRANSACTIONS on Information Vol.E89-D No.12 pp.2933-2938
- Publication Date
- 2006/12/01
- Publicized
- Online ISSN
- 1745-1361
- DOI
- 10.1093/ietisy/e89-d.12.2933
- Type of Manuscript
- PAPER
- Category
- Automata and Formal Language Theory
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Akio FUJIYOSHI, "Analogical Conception of Chomsky Normal Form and Greibach Normal Form for Linear, Monadic Context-Free Tree Grammars" in IEICE TRANSACTIONS on Information,
vol. E89-D, no. 12, pp. 2933-2938, December 2006, doi: 10.1093/ietisy/e89-d.12.2933.
Abstract: This paper presents the analogical conception of Chomsky normal form and Greibach normal form for linear, monadic context-free tree grammars (LM-CFTGs). LM-CFTGs generate the same class of languages as four well-known mildly context-sensitive grammars. It will be shown that any LM-CFTG can be transformed into equivalent ones in both normal forms. As Chomsky normal form and Greibach normal form for context-free grammars (CFGs) play a very important role in the study of formal properties of CFGs, it is expected that the Chomsky-like normal form and the Greibach-like normal form for LM-CFTGs will provide deeper analyses of the class of languages generated by mildly context-sensitive grammars.
URL: https://global.ieice.org/en_transactions/information/10.1093/ietisy/e89-d.12.2933/_p
Copy
@ARTICLE{e89-d_12_2933,
author={Akio FUJIYOSHI, },
journal={IEICE TRANSACTIONS on Information},
title={Analogical Conception of Chomsky Normal Form and Greibach Normal Form for Linear, Monadic Context-Free Tree Grammars},
year={2006},
volume={E89-D},
number={12},
pages={2933-2938},
abstract={This paper presents the analogical conception of Chomsky normal form and Greibach normal form for linear, monadic context-free tree grammars (LM-CFTGs). LM-CFTGs generate the same class of languages as four well-known mildly context-sensitive grammars. It will be shown that any LM-CFTG can be transformed into equivalent ones in both normal forms. As Chomsky normal form and Greibach normal form for context-free grammars (CFGs) play a very important role in the study of formal properties of CFGs, it is expected that the Chomsky-like normal form and the Greibach-like normal form for LM-CFTGs will provide deeper analyses of the class of languages generated by mildly context-sensitive grammars.},
keywords={},
doi={10.1093/ietisy/e89-d.12.2933},
ISSN={1745-1361},
month={December},}
Copy
TY - JOUR
TI - Analogical Conception of Chomsky Normal Form and Greibach Normal Form for Linear, Monadic Context-Free Tree Grammars
T2 - IEICE TRANSACTIONS on Information
SP - 2933
EP - 2938
AU - Akio FUJIYOSHI
PY - 2006
DO - 10.1093/ietisy/e89-d.12.2933
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E89-D
IS - 12
JA - IEICE TRANSACTIONS on Information
Y1 - December 2006
AB - This paper presents the analogical conception of Chomsky normal form and Greibach normal form for linear, monadic context-free tree grammars (LM-CFTGs). LM-CFTGs generate the same class of languages as four well-known mildly context-sensitive grammars. It will be shown that any LM-CFTG can be transformed into equivalent ones in both normal forms. As Chomsky normal form and Greibach normal form for context-free grammars (CFGs) play a very important role in the study of formal properties of CFGs, it is expected that the Chomsky-like normal form and the Greibach-like normal form for LM-CFTGs will provide deeper analyses of the class of languages generated by mildly context-sensitive grammars.
ER -
English
