Two Ways of Introducing Alternation into Context-Free Grammars and Pushdown Automata

Etsuro MORIYA; Friedrich OTTO

doi:10.1093/ietisy/e90-d.6.889

Two Ways of Introducing Alternation into Context-Free Grammars and Pushdown Automata

Etsuro MORIYA, Friedrich OTTO

Full Text Views

0

Share
Cite this

Summary :

Two ways of introducing alternation for context-free grammars and pushdown automata are compared. One is the usual way which combines "states" with alternation [1], [4], [7], and the other is the way used in [6] to define the alternating context-free grammar, i.e., alternation is governed by the variables of the grammar. In this paper the latter way is taken over to define a new type of alternating pushdown automaton by combining the "pushdown symbols" of the pushdown automaton with alternation. We have derived a characterization of the original alternating context-free grammars in terms of such a new type of alternating pushdown automaton without states. It is also shown that, if (non-alternating) states are introduced as an additional feature for this type of pushdown automaton, then the resulting alternating pushdown automaton has exactly the same expressive power as the original alternating pushdown automaton.

Publication: IEICE TRANSACTIONS on Information Vol.E90-D No.6 pp.889-894

Publication Date: 2007/06/01

Publicized

Online ISSN: 1745-1361

DOI: 10.1093/ietisy/e90-d.6.889

Type of Manuscript: PAPER

Category: Automata and Formal Language Theory

Cite this

Copy

Etsuro MORIYA, Friedrich OTTO, "Two Ways of Introducing Alternation into Context-Free Grammars and Pushdown Automata" in IEICE TRANSACTIONS on Information, vol. E90-D, no. 6, pp. 889-894, June 2007, doi: 10.1093/ietisy/e90-d.6.889.
Abstract: Two ways of introducing alternation for context-free grammars and pushdown automata are compared. One is the usual way which combines "states" with alternation [1], [4], [7], and the other is the way used in [6] to define the alternating context-free grammar, i.e., alternation is governed by the variables of the grammar. In this paper the latter way is taken over to define a new type of alternating pushdown automaton by combining the "pushdown symbols" of the pushdown automaton with alternation. We have derived a characterization of the original alternating context-free grammars in terms of such a new type of alternating pushdown automaton without states. It is also shown that, if (non-alternating) states are introduced as an additional feature for this type of pushdown automaton, then the resulting alternating pushdown automaton has exactly the same expressive power as the original alternating pushdown automaton.
URL: https://globals.ieice.org/en_transactions/information/10.1093/ietisy/e90-d.6.889/_p

Copy

@ARTICLE{e90-d_6_889,
author={Etsuro MORIYA, Friedrich OTTO, },
journal={IEICE TRANSACTIONS on Information},
title={Two Ways of Introducing Alternation into Context-Free Grammars and Pushdown Automata},
year={2007},
volume={E90-D},
number={6},
pages={889-894},
abstract={Two ways of introducing alternation for context-free grammars and pushdown automata are compared. One is the usual way which combines "states" with alternation [1], [4], [7], and the other is the way used in [6] to define the alternating context-free grammar, i.e., alternation is governed by the variables of the grammar. In this paper the latter way is taken over to define a new type of alternating pushdown automaton by combining the "pushdown symbols" of the pushdown automaton with alternation. We have derived a characterization of the original alternating context-free grammars in terms of such a new type of alternating pushdown automaton without states. It is also shown that, if (non-alternating) states are introduced as an additional feature for this type of pushdown automaton, then the resulting alternating pushdown automaton has exactly the same expressive power as the original alternating pushdown automaton.},
keywords={},
doi={10.1093/ietisy/e90-d.6.889},
ISSN={1745-1361},
month={June},}

Copy

TY - JOUR
TI - Two Ways of Introducing Alternation into Context-Free Grammars and Pushdown Automata
T2 - IEICE TRANSACTIONS on Information
SP - 889
EP - 894
AU - Etsuro MORIYA
AU - Friedrich OTTO
PY - 2007
DO - 10.1093/ietisy/e90-d.6.889
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E90-D
IS - 6
JA - IEICE TRANSACTIONS on Information
Y1 - June 2007
AB - Two ways of introducing alternation for context-free grammars and pushdown automata are compared. One is the usual way which combines "states" with alternation [1], [4], [7], and the other is the way used in [6] to define the alternating context-free grammar, i.e., alternation is governed by the variables of the grammar. In this paper the latter way is taken over to define a new type of alternating pushdown automaton by combining the "pushdown symbols" of the pushdown automaton with alternation. We have derived a characterization of the original alternating context-free grammars in terms of such a new type of alternating pushdown automaton without states. It is also shown that, if (non-alternating) states are introduced as an additional feature for this type of pushdown automaton, then the resulting alternating pushdown automaton has exactly the same expressive power as the original alternating pushdown automaton.
ER -