Some remarks on state grammars and matrix grammars

Etsuro Moriya

doi:10.1016/S0019-9958(73)90884-X

Some remarks on state grammars and matrix grammars

Etsuro Moriya^*

^*Corresponding author for this work

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

9 Citations (Scopus)

Abstract

The context-free matrix grammar and the state grammar without any restriction in applying productions are considered. It turned out that these grammars are equivalent in the generative power. Another type of state grammar called the state grammar with unconditional transfer is introduced, and it is shown that each context-free matrix language is a homomorphic image of the intersection of a state language with unconditional transfer and a regular set.

Original language	English
Pages (from-to)	48-57
Number of pages	10
Journal	Information and control
Volume	23
Issue number	1
DOIs	https://doi.org/10.1016/S0019-9958(73)90884-X
Publication status	Published - 1973
Externally published	Yes

ASJC Scopus subject areas

Engineering(all)

Access to Document

10.1016/S0019-9958(73)90884-X

Cite this

@article{c0cfa242de2c4ca99379b5b29110ea49,

title = "Some remarks on state grammars and matrix grammars",

abstract = "The context-free matrix grammar and the state grammar without any restriction in applying productions are considered. It turned out that these grammars are equivalent in the generative power. Another type of state grammar called the state grammar with unconditional transfer is introduced, and it is shown that each context-free matrix language is a homomorphic image of the intersection of a state language with unconditional transfer and a regular set.",

author = "Etsuro Moriya",

year = "1973",

doi = "10.1016/S0019-9958(73)90884-X",

language = "English",

volume = "23",

pages = "48--57",

journal = "Information and control",

issn = "0019-9958",

publisher = "Elsevier Inc.",

number = "1",

}

TY - JOUR

T1 - Some remarks on state grammars and matrix grammars

AU - Moriya, Etsuro

PY - 1973

Y1 - 1973

N2 - The context-free matrix grammar and the state grammar without any restriction in applying productions are considered. It turned out that these grammars are equivalent in the generative power. Another type of state grammar called the state grammar with unconditional transfer is introduced, and it is shown that each context-free matrix language is a homomorphic image of the intersection of a state language with unconditional transfer and a regular set.

AB - The context-free matrix grammar and the state grammar without any restriction in applying productions are considered. It turned out that these grammars are equivalent in the generative power. Another type of state grammar called the state grammar with unconditional transfer is introduced, and it is shown that each context-free matrix language is a homomorphic image of the intersection of a state language with unconditional transfer and a regular set.

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

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

U2 - 10.1016/S0019-9958(73)90884-X

DO - 10.1016/S0019-9958(73)90884-X

M3 - Article

AN - SCOPUS:0015655081

SN - 0019-9958

VL - 23

SP - 48

EP - 57

JO - Information and control

JF - Information and control

IS - 1

ER -

Some remarks on state grammars and matrix grammars

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this