Refinement of Representation Theorems for Context-Free Languages
Summary :
In this paper, we obtain some refinement of representation theorems for context-free languages by using Dyck languages, insertion systems, strictly locally testable languages, and morphisms. For instance, we improved the Chomsky-Schützenberger representation theorem and show that each context-free language L can be represented in the form L=h(D ∪ R), where D is a Dyck language, R is a strictly 3-testable language, and h is a morphism. A similar representation for context-free languages can be obtained, using insertion systems of weight (3,0) and strictly 4-testable languages.
- Publication
- IEICE TRANSACTIONS on Information Vol.E93-D No.2 pp.227-232
- Publication Date
- 2010/02/01
- Publicized
- Online ISSN
- 1745-1361
- DOI
- 10.1587/transinf.E93.D.227
- Type of Manuscript
- Special Section PAPER (Special Section on Foundations of Computer Science)
- Category
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
Kaoru FUJIOKA, "Refinement of Representation Theorems for Context-Free Languages" in IEICE TRANSACTIONS on Information,
vol. E93-D, no. 2, pp. 227-232, February 2010, doi: 10.1587/transinf.E93.D.227.
Abstract: In this paper, we obtain some refinement of representation theorems for context-free languages by using Dyck languages, insertion systems, strictly locally testable languages, and morphisms. For instance, we improved the Chomsky-Schützenberger representation theorem and show that each context-free language L can be represented in the form L=h(D ∪ R), where D is a Dyck language, R is a strictly 3-testable language, and h is a morphism. A similar representation for context-free languages can be obtained, using insertion systems of weight (3,0) and strictly 4-testable languages.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.E93.D.227/_p
Copy
@ARTICLE{e93-d_2_227,
author={Kaoru FUJIOKA, },
journal={IEICE TRANSACTIONS on Information},
title={Refinement of Representation Theorems for Context-Free Languages},
year={2010},
volume={E93-D},
number={2},
pages={227-232},
abstract={In this paper, we obtain some refinement of representation theorems for context-free languages by using Dyck languages, insertion systems, strictly locally testable languages, and morphisms. For instance, we improved the Chomsky-Schützenberger representation theorem and show that each context-free language L can be represented in the form L=h(D ∪ R), where D is a Dyck language, R is a strictly 3-testable language, and h is a morphism. A similar representation for context-free languages can be obtained, using insertion systems of weight (3,0) and strictly 4-testable languages.},
keywords={},
doi={10.1587/transinf.E93.D.227},
ISSN={1745-1361},
month={February},}
Copy
TY - JOUR
TI - Refinement of Representation Theorems for Context-Free Languages
T2 - IEICE TRANSACTIONS on Information
SP - 227
EP - 232
AU - Kaoru FUJIOKA
PY - 2010
DO - 10.1587/transinf.E93.D.227
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E93-D
IS - 2
JA - IEICE TRANSACTIONS on Information
Y1 - February 2010
AB - In this paper, we obtain some refinement of representation theorems for context-free languages by using Dyck languages, insertion systems, strictly locally testable languages, and morphisms. For instance, we improved the Chomsky-Schützenberger representation theorem and show that each context-free language L can be represented in the form L=h(D ∪ R), where D is a Dyck language, R is a strictly 3-testable language, and h is a morphism. A similar representation for context-free languages can be obtained, using insertion systems of weight (3,0) and strictly 4-testable languages.
ER -
English
