On purely morphic characterizations of context-free languages

Takashi Yokomori

doi:10.1016/0304-3975(87)90038-7

On purely morphic characterizations of context-free languages

Takashi Yokomori^*

^*Corresponding author for this work

Research output: Contribution to journal › Article › peer-review

3 Citations (Scopus)

Abstract

In this paper we show the following: For any λ-free context-free language L there effectively exist a weak coding g, a homomorphism h such that L=gh^-1 ({divides}cD₂), where D₂ is the Dyck set over a two-letter alphabet. As an immediate corollary it follows that for any λ-free context-free language L there exist a weak coding g and a mapping F such that L=gF^-1({divides}c).

Original language	English
Pages (from-to)	301-308
Number of pages	8
Journal	Theoretical Computer Science
Volume	51
Issue number	3
DOIs	https://doi.org/10.1016/0304-3975(87)90038-7
Publication status	Published - 1987
Externally published	Yes

ASJC Scopus subject areas

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1016/0304-3975(87)90038-7

Cite this

@article{3d1088349b3f42e691e7ea028b799121,

title = "On purely morphic characterizations of context-free languages",

abstract = "In this paper we show the following: For any λ-free context-free language L there effectively exist a weak coding g, a homomorphism h such that L=gh-1 ({divides}cD2), where D2 is the Dyck set over a two-letter alphabet. As an immediate corollary it follows that for any λ-free context-free language L there exist a weak coding g and a mapping F such that L=gF-1({divides}c).",

author = "Takashi Yokomori",

year = "1987",

doi = "10.1016/0304-3975(87)90038-7",

language = "English",

volume = "51",

pages = "301--308",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier",

number = "3",

}

TY - JOUR

T1 - On purely morphic characterizations of context-free languages

AU - Yokomori, Takashi

PY - 1987

Y1 - 1987

N2 - In this paper we show the following: For any λ-free context-free language L there effectively exist a weak coding g, a homomorphism h such that L=gh-1 ({divides}cD2), where D2 is the Dyck set over a two-letter alphabet. As an immediate corollary it follows that for any λ-free context-free language L there exist a weak coding g and a mapping F such that L=gF-1({divides}c).

AB - In this paper we show the following: For any λ-free context-free language L there effectively exist a weak coding g, a homomorphism h such that L=gh-1 ({divides}cD2), where D2 is the Dyck set over a two-letter alphabet. As an immediate corollary it follows that for any λ-free context-free language L there exist a weak coding g and a mapping F such that L=gF-1({divides}c).

UR - http://www.scopus.com/inward/record.url?scp=0023496853&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0023496853&partnerID=8YFLogxK

U2 - 10.1016/0304-3975(87)90038-7

DO - 10.1016/0304-3975(87)90038-7

M3 - Article

AN - SCOPUS:0023496853

SN - 0304-3975

VL - 51

SP - 301

EP - 308

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - 3

ER -

On purely morphic characterizations of context-free languages

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this