Parikh's theorem: A simple and direct automaton construction

Javier Esparza; Pierre Ganty; Stefan Kiefer; Michael Luttenberger

doi:10.1016/j.ipl.2011.03.019

Parikh's theorem: A simple and direct automaton construction

Javier Esparza
, Pierre Ganty
, Stefan Kiefer
, Michael Luttenberger

Informatics 7 - Chair of Theoretical Computer Science

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

48 Scopus citations

Abstract

Parikh-s theorem states that the Parikh image of a context-free language is semilinear or, equivalently, that every context-free language has the same Parikh image as some regular language. We present a very simple construction that, given a context-free grammar, produces a finite automaton recognizing such a regular language.

Original language	English
Pages (from-to)	614-619
Number of pages	6
Journal	Information Processing Letters
Volume	111
Issue number	12
DOIs	https://doi.org/10.1016/j.ipl.2011.03.019
State	Published - 15 Jun 2011

Keywords

Context-free language
Formal languages
Parikh image
Regular language

Access to Document

10.1016/j.ipl.2011.03.019

Cite this

@article{06b44507a1ca45aea67eb79b45dce064,

title = "Parikh's theorem: A simple and direct automaton construction",

abstract = "Parikh-s theorem states that the Parikh image of a context-free language is semilinear or, equivalently, that every context-free language has the same Parikh image as some regular language. We present a very simple construction that, given a context-free grammar, produces a finite automaton recognizing such a regular language.",

keywords = "Context-free language, Formal languages, Parikh image, Regular language",

author = "Javier Esparza and Pierre Ganty and Stefan Kiefer and Michael Luttenberger",

note = "Funding Information: 1This author is sponsored by the Comunidad de Madrid{\textquoteright}s Program prometidos-cm (S2009TIC-1465), by the people-cofund{\textquoteright}s program amarout (PCOFUND-2008-229599), and by the Spanish Ministry of Science and Innovation (TIN2010-20639). Funding Information: 2 This author is supported by a postdoctoral fellowship of the German Academic Exchange Service (DAAD).",

year = "2011",

month = jun,

day = "15",

doi = "10.1016/j.ipl.2011.03.019",

language = "English",

volume = "111",

pages = "614--619",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier B.V.",

number = "12",

}

TY - JOUR

T1 - Parikh's theorem

T2 - A simple and direct automaton construction

AU - Esparza, Javier

AU - Ganty, Pierre

AU - Kiefer, Stefan

AU - Luttenberger, Michael

N1 - Funding Information: 1This author is sponsored by the Comunidad de Madrid’s Program prometidos-cm (S2009TIC-1465), by the people-cofund’s program amarout (PCOFUND-2008-229599), and by the Spanish Ministry of Science and Innovation (TIN2010-20639). Funding Information: 2 This author is supported by a postdoctoral fellowship of the German Academic Exchange Service (DAAD).

PY - 2011/6/15

Y1 - 2011/6/15

N2 - Parikh-s theorem states that the Parikh image of a context-free language is semilinear or, equivalently, that every context-free language has the same Parikh image as some regular language. We present a very simple construction that, given a context-free grammar, produces a finite automaton recognizing such a regular language.

AB - Parikh-s theorem states that the Parikh image of a context-free language is semilinear or, equivalently, that every context-free language has the same Parikh image as some regular language. We present a very simple construction that, given a context-free grammar, produces a finite automaton recognizing such a regular language.

KW - Context-free language

KW - Formal languages

KW - Parikh image

KW - Regular language

UR - https://www.scopus.com/pages/publications/79953663489

U2 - 10.1016/j.ipl.2011.03.019

DO - 10.1016/j.ipl.2011.03.019

M3 - Article

AN - SCOPUS:79953663489

SN - 0020-0190

VL - 111

SP - 614

EP - 619

JO - Information Processing Letters

JF - Information Processing Letters

IS - 12

ER -

Parikh's theorem: A simple and direct automaton construction

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this