=Paper=
{{Paper
|id=None
|storemode=property
|title=Flip-pushdown automata: nondeterministic $\epsilon$-moves can be removed
|pdfUrl=https://ceur-ws.org/Vol-788/paper3.pdf
|volume=Vol-788
|dblpUrl=https://dblp.org/rec/conf/itat/DurisK11
}}
==Flip-pushdown automata: nondeterministic $\epsilon$-moves can be removed==
https://ceur-ws.org/Vol-788/paper3.pdf
Flip-pushdown automata:
nondeterministic ε-moves can be removed⋆
Pavol Ďuriš and Marek Košta
Comenius University, Bratislava, Slovakia,
duris@dcs.fmph.uniba.sk
kosta1@st.fmph.uniba.sk
Abstract. Flip-pushdown automaton is pushdown au- The problem we deal with is the power of ε-moves.
tomaton which has ability to flip its pushdown through- Well-known and famous result by Greibach [5] is the
out the computation. This model was introduced in [3] by so-called Greibach normal form for the context-free
Sarkar. Here we solve in the affirmative the following open grammar. With this result one can easily prove that for
problem posed by Holzer and Kutrib in [1]: What is the every pushdown automaton ε-free pushdown automa-
power of ε-moves for nondeterministic flip-pushdown au-
ton can be constructed. By ε-free pushdown automa-
tomata – can they be removed without affecting the compu-
tational capacity? (ε denotes the empty word.) Moreover,
ton we mean automaton that does not use ε-moves.
we prove here that the family of languages recognized by the Our main result parallels this nicely: for every flip-
deterministic variant of the flip-pushdown automata (with pushdown automaton other ε-free flip-pushdown au-
k-pushdown reversals) is closed under intersection with reg- tomaton accepting the same language can be found.
ular sets, complement and inverse homomorphism, but it is Moreover, our proof of this fact is constructive. Of
not closed under union, intersection, (non-erasing) homo- course we will use Greibach normal form quite exten-
morphism, reverse, concatenation and (positive) iteration. sively.
Finally, we formulate some new questions and pose new In section 2 we give necessary formal definitions
problems. and cite the most important Theorems. Section 3 is the
central section of the paper, here we state and prove
our main result – that ε-moves can be removed with-
1 Introduction out affecting computational power of the nondetermin-
istic flip-pushdown automaton model. Some closure
A flip-pushdown automaton, introduced by Sarkar [3], properties of families of languages described by de-
is an ordinary one-way pushdown automaton with the terministic flip-pushdown automata are discussed in
ability to flip its pushdown during the computation. It section 4. Finally, we summarize our results and pose
is known [3] that the flip-pushdown automata without new problems in section 5.
any limit on the number of flips are equally powerful
to Turing machines.
2 Preliminaries
Holzer and Kutrib [1, 2] have introduced the so-
called “flip-pushdown input-reversal technique” and The reader should be familiar with basic facts from
using it they have shown that k+1 pushdown reversals formal language theory, where we refer to standard
are more powerful than k for deterministic and non- textbook on this subject [4]. We use ε to denote empty
deterministic flip-pushdown automata, and, nondeter- word, powerset of a set S by 2S and length of w by |w|.
minism is more powerful than determinism for flip-
pushdown automata with constant number of flips. Definition 1. A nondeterministic flip-pushdown au-
Another use of this technique led to the fact that tomaton (NFPDA) is a system A = (Q, Σ, Γ , δ, ∆,
languages accepted by flip-pushdown automata using q0 , Z0 , F ), where Q is a finite set of states, Σ is a fi-
constant number of flips can be accepted by linear nite input alphabet, Γ is a finite pushdown alphabet,
bounded automata, so investigated language classes lie δ is a mapping from Q × (Σ ∪ {ε}) × Γ to finite
between context-free and extended context-sensitive subsets of Q × Γ ∗ called the transition function, ∆ is
language classes in Chomsky hierarchy. These papers a mapping from Q to 2Q , q0 is the initial state, Z0 ∈ Γ
raised also some new questions and pointed to some is a specific pushdown symbol, called the bottom-of-
interesting problems. pushdown symbol, which initially appears on the push-
down store, and F ⊆ Q is the set of final states.
⋆
This work was supported by Slovak Grant Agency for
Science (VEGA) under contract #1/0726/09 “Algorith- A configuration of this automaton is a triple
mics and Complexity Aspects of Information Process- (q, w, γ), where q ∈ Q, w ∈ Σ ∗ and γ ∈ Γ ∗ . When flip-
ing”. pushdown automaton A is in configuration (q, w, γ),
16 Pavol Ďuriš, Marek Košta
then it is in state q, remaining input is w and stack Theorem 1 ([2]). Let k ≥ 0. Then language L is
content is γ. Flip-pushdown automaton has two pos- accepted by a nondeterministic flip-pushdown automa-
sibilities how to change configuration: via δ-function ton M = (Q, Σ, Γ, δ, ∆, q0 , Z0 , F ) by final state with at
or via ∆-function. We write (q, aw, γZ) ⊢A (p, w, γα) most k + 1 pushdown reversals, i.e. L = T≤k+1 (M ), if
if and only if (p, α) ∈ δ(q, a, Z) when δ-step is taken. and only if language LR = {wv R such that (q0 , w, Z0 )
In second case we write (q, w, Z0 γ) ⊢A (p, w, Z0 γ R ) if ⊢∗M (q1 , ε, Z0 γ) with k reversals, q2 ∈ ∆(q1 ) and
and only if p ∈ ∆(q). Intuitively, the first case is the (q2 , v, Z0 γ R ) ⊢∗M (q3 , ε, ε) without any reversal} is ac-
standard pushdown computational step. Second case, cepted by a nondeterministic flip-pushdown automaton
however, is new possibility (in comparison to standard M ′ by final state with at most k pushdown reversals,
pushdown automaton) and in this case content of the i.e. LR = T≤k (M ′ ). The same holds when acceptance
pushdown is reversed (flipped). So the flip-pushdown by empty pushdown is considered. Moreover, automa-
automaton has two possibilities in any configuration: ton M ′ can be effectively constructed from automa-
either apply δ-function or apply ∆-function. Nonde- ton M and vice versa.
terministic choice is made to choose the next config-
uration. Note that when A is flipping pushdown con- This Theorem provides trade-off between number
tent then special symbol (Z0 ) has to be at the bottom of flips and number of reversals. The number of flips
of the pushdown and is not flipped. The reflexive and can be reduced by one when correct suffixes of words
transitive closure of relation ⊢A just defined is denoted in L are reversed. But the real power of this Theorem
by ⊢∗A . The subscript A will be omitted whenever the is revealed when it is applied k times on language L ac-
meaning is clear. cepted by some k-flip pushdown automaton. Then we
Let k ≥ 0. Then we define the language accepted get context-free language L′ that has strong connec-
by flip-pushdown automaton A by final state and by at tion with language L. Simply speaking, we get words
most k pushdown reversals as T≤k (A) = {w ∈ Σ ∗ such in L′ first by reversing some correct suffixes of words
that (q0 , w, Z0 ) ⊢∗A (q, ε, γ) with at most k pushdown in L and then applying this process inductively.
reversals, for some γ ∈ Γ ∗ and q ∈ F }.
Language accepted by empty pushdown and by at
most k pushdown reversals is defined as N≤k (A) = 3 Main result
{w ∈ Σ ∗ such that (q0 , w, Z0 ) ⊢∗A (q, ε, ε) with at
most k pushdown reversals}. When accepting by In this section we will prove that for every k-flip push-
empty pushdown, set of the final states is usually de- down automaton M , a k-flip pushdown automaton M̄
fined to be empty. Similarly, one can also define can be constructed in such a way that M̄ does not
N=k (A) or T=k (A) with apparent meaning. use ε-steps. This means that δ(q, ε, Z) = ∅ holds for
Class of languages accepted by nondeterministic every q, Z and δ-function of M̄ and M̄ accepts the
flip-pushdown automata by at most k flips (i.e. those same language as M .
languages L for which there is A, such that
T≤k (A) = L) is denoted by L (NFPDA(≤ k)). Broader
3.1 Main idea
class containing all these classes is
∞
∪ Suppose we have a language L that is accepted by
L (NFPDA(≤ k)) = L (NFPDA(fin)). some k-flip pushdown automaton M = (Q, Σ, Γ, δ, ∆,
i=0 q0 , Z0 , ∅) by empty pushdown. In previously defined
notation this means that L = N=k (M ). Let Lk be the
When dealing with nondeterministic flip-pushdown language containing the words of the form v0 $v1 $ . . .
automata the mode of acceptance does not change the $vk $ such that w = v0 v1 . . . vk ∈ L, and for w there
computational power of the model. In deterministic is an accepting computation of M on w during which
case, however, situation is a little bit more compli- M makes a flip of the pushdown content at the end of
cated. For more information we refer to [1]. each vi for 0 ≤ i ≤ k − 1. New automaton M ′ accept-
Just for completeness, let us define Greibach nor- ing Lk can be easily constructed: just simulate M and
mal form. after each flip symbol $ must be read or computation
Definition 2. Context free grammar G = (N, T, P, S) will stuck. Symbol $ must be also read at the end of
is in Greibach normal form if all rules are of the form the word.
A → aβ where A ∈ N , a ∈ T and β ∈ N ∗ . So we have marked places in words accepted by M
where flip of pushdown occurred. We will also con-
Already mentioned “flip-pushdown input-reversal” struct languages Lk−1 , . . . , L0 in this way: language Li
technique is very powerful tool we will use extensively is constructed from language Li+1 (0 ≤ i ≤ k − 1)
in the following. by applying “flip-pushdown input-reversal technique”,
Flip pushdown automata 17
see Theorem 1. So Li is accepted by some i-flip push- Here αi is non-empty string of nonterminals, other
down automaton which can be constructed according symbols are terminal.
to Theorem 1. These facts are formally described in If we were able to reverse and regulate this deriva-
two following Lemmas. tion in right way we could obtain “derivation” of word
wk instead of w0 (w0 and wk are from Lemma 2). This
Lemma 1. Let Lk be the previously defined language. means that if we could after (1) reverse string α and
0
Let Lk , . . . , L0 be the languages, where the language also reverse terminal words derived from these non-
Li−1 is obtained from language Li by one application terminals (i.e. derive in grammar G obtained from G
1 0
of Theorem 1 for 1 ≤ i ≤ k. Then word w = by reversing right-hand side of each production), we
could obtain something like this:
v0 $v1 $ . . . $vi−1 $vi $vi+1 $ . . . $vk−1 $vk $
S0 ⇒∗G0 v0 α0 reverse nonterminal string
is in language Li if and only if word w′ =
v0 α0R now continue in G1
v0 $v1 $ . . . $vi−1 $vkR $vk−1
R R
$ . . . $vi+1 $viR $ ⇒∗G1 v0 $v1 β β is nonterminal string in G1
is in language Li−1 for 1 ≤ i ≤ k. The main idea of the previous process is this. We want
Proof. Quite obvious. The last flip in computation on to simulate the leftmost derivation (in grammar G0 )
word w occurs after subword vi . Because symbol $ by pushdown automaton, storing nonterminal string
is new and also from formulation of Theorem 1 stated on the stack. When reversal takes place, automaton
correspondence between words from Li and Li−1 holds. will simulate leftmost derivation in G1 (we will call it
⊓
⊔ reverse grammar) and so on. By continuing this sim-
ulation in suitable grammars making reversals along
Lemma 2. When k = 2l then word w0 = the way we can obtain valid accepting computation
R
on word wk . Deeper analysis will follow but first we
v0 $v2 $ . . . $v2l $v2l−1 $ . . . $v3R $v1R $ need some notation based on (1).
belongs to language L0 if and only if word wk = v0 $v1 $ α0 = A1 . . . An (2)
. . . $vk $ belongs to Lk . In case k = 2l + 1 words in L0
Ai ⇒∗G0 xi ∈ T ∗
have form
u = x1 . . . xn
R R
v0 $v2 $ . . . $v2l $v2l+1 $v2l−1 $ . . . $v3R $v1R $ R
u = $v2 $v4 . . . $v2l $v2l−1 $ . . . $v3R $v1R $
Proof. Just apply Lemma 1 inductively k times. ⊓
⊔ uR = $v1 $v3 $ . . . $v2l−1 $v2l
R
$ . . . $v4R $v2R $
In the following we assume for simplicity that We will use the concept of reverse grammar exten-
k = 2l, case when k = 2k + 1 is proved similarly. We sively in the following so here is formal definition.
will exploit correspondence between words in L0 and
Definition 3. We say that context-free grammar H =
those in Lk stated in Lemma 2. Language L0 is by def-
(NH , T, PH , SH ) is reverse grammar to context-free
inition context-free so there is Greibach normal form
grammar I = (NI , T, PI , SI ) if the following condi-
context free grammar generating it. We want to sim-
tions hold:
ulate leftmost derivations in this grammar (and oth-
ers constructed from this one) with flip-pushdown au- 1. H is in Greibach normal form
tomaton. 2. NH ∩ NI = NI
Let us have context-free grammar G0 = 3. (∀ξ ∈ NI )(∀z ∈ T ∗ ) ξ ⇒∗H z R ⇐⇒ ξ ⇒∗I z
(N0 , Σ ∪{$}, P0 , S0 ), such that L(G0 ) = L0 . Leftmost
derivation of word w0 ∈ L0 in grammar G0 looks like Lemma 3. Assume that H is reverse grammar to I.
this: Then for every α (non-empty nonterminal string of
grammar I) and v (terminal string) we have:
S0 ⇒∗ v0 α0 ⇒∗ (1)
α ⇒∗I v if and only if αR ⇒∗H v R (3)
⇒∗ v0 $v2 α2 ⇒∗ v0 $v2 $v4 α4 ⇒∗
⇒∗ v0 $v2 $v4 . . . $v2l α2l ⇒∗ Proof. Easy induction on the length of α. From defi-
⇒∗ v0 $v2 $v4 . . . $v2l $v2l−1
R
α2l−1 ⇒∗ nition 3 we see that the statement holds when |α| = 1.
Assume that the statement hold for all α of length k.
⇒∗ v0 $v2 $v4 . . . $v2l $v2l−1
R R
$v2l−3 α2l−3 ⇒∗
∗
Now let αA ⇒∗I vα vA . By induction hypothesis and
∗
⇒ ··· ⇒ definition 3 this is equivalent to AαR ⇒∗H vA R R
vα . So
⇒∗ v0 $v2 $v4 . . . $v2l $v2l−1
R
$ . . . $v3R $v1R $ = w0 the statement of the Lemma follows by induction. ⊔ ⊓
18 Pavol Ďuriš, Marek Košta
We want to construct flip-pushdown automaton M f Construction of Reverse Grammars. Initially, we have
without ε-moves, which will simulate leftmost deriva- grammar G0 . We show construction of Gi when Gi−1
tions in G0 , . . . , Gk (here Gi+1 is reverse to Gi ) as fol- is already constructed. So assume that we have gram-
lows. On input wk , M f is going to verify if wk belongs mar Gi−1 = (Ni , Σ, Pi , Si ). We want to construct
to Lk . Initial configuration of M f is (q0 , wk , S0 ). After grammar Gi which satisfy all conditions in definition 3.
simulating the leftmost derivation (in G0 ) the config- From these the most important is the third condition.
uration will be (q, $v1 $ . . . $vk $, An . . . A1 ) 1 . Flip now Consider language LA = {uR | A ⇒∗Gi−1 u} for every
takes place and M f will continue simulating G1 – re- nonterminal A of Gi−1 . Greibach normal form gram-
verse grammar to grammar G0 . From Lemma 3 and (2) mar GA for this language can be constructed by well-
we have: known construction. From these grammars one can get
grammar Gi satisfying all three conditions in defini-
Ai ⇒∗G1 xR
i
tion 3 easily – just by union of rules and nonterminal.
Some renaming, however, must be done to ensure the
uR = xR R
n . . . x1 second condition of definition 3.
uR = $v1 $v3 $ . . . $v2l−1 $v2l
R
$ . . . $v4R $v2R $ (4)
Technical Consideration. In definition 1 we wanted to
From these facts it is apparent that be coherent with established formalism. But this def-
inition is a little bit cumbersome. Our idea is to rep-
An . . . A1 ⇒∗G1 $v1 B1 B2 . . . Bm resent sentential form on the stack and do computa-
tion with this representation (doing flips and simulate
where Bi are nonterminals of grammar G1 . So M f will grammars Gi ). So it is inconvenient to bother with
continue from configuration (p,$v1 $ . . .$vk $, A1 . . .An ), special Z0 symbol and convention that it is always at
simulating G1 , to configuration (r, $v2 $ . . . $vk $, the bottom and never flipped. For the sake of simplic-
Bm . . . B1 ). ity, we will formally do our construction without this
We believe that the main idea is now clear. The restriction. But we must note that this in no way spoils
most important point here is that we are able to sim- the result or prevents construction in accordance with
ulate leftmost derivation in G0 by standard δ-steps of definition 1. This construction is straightforward but
flip-pushdown automaton with sentential form on the technical – some simulation of bottom of pushdown,
stack. Then flip can be done and we can continue by some information stored in states, new marked push-
simulating derivation in G1 which is reverse grammar down symbols and so on. The most important point
to G0 . This process of simulating and flipping will con- is that all these things can be done without any use of
tinue up to grammar Gk . Crucial here is that all these ε-steps. So in the following construction ∆-steps cause
grammars used along the way are in Greibach normal reversal of the whole pushdown word and no special
form so M f will not use ε-moves when simulating these symbol must be at the bottom of the stack. So senten-
grammars. tial form is represented “as is” on the stack.
Let Mf = (Q, Σ ∪{$}, Γ , δ, ∆, q0 , S0 , {qF }), where
3.2 Proof Q = {q0 , q1 , . . . , qk } ∪ {q1 , . . . , qk } ∪ {qF },
Σ is alphabet of M ′ and $ is new symbol,
′
So we have M accepting language Lk (see the begin- Γ = {A | where A is nontermial of Gi , 0 ≤ i ≤ k},
ning of subsection 3.1) by empty pushdown and by
∆(qi ) = {qi+1 } ∧ 0 ≤ i ≤ k − 1.
exactly k flips. By Lemma 2, L0 can be generated by
some context-free grammar G0 = (N0 , Σ, P0 , S0 ). Standard pushdown moves (i.e. δ-steps) will ensure the
We want to construct automaton M f without ε-moves simulation of the leftmost derivation in grammars Gi .
which will accept Lk by final state and by exactly k re- This can be seen from next lines:
versals. However, this acceptation mode will be more
δ(q0 , a, S0 ) ∋ (q0 , β R ) ⇔ a ∈ Σ ∧ S0 → aβ ∈ P0
special than this: from construction it will be appar-
ent that Mf will accept only in configuration in which δ(qi , $, Z) ∋ (qi , β )
R
⇔ Z → $β ∈ Pi
final state is reached, pushdown is empty and exactly δ(qi , a, Z) ∋ (qi , β R ) ⇔ a ∈ Σ ∧ Z → aβ ∈ Pi
k flips took place. δ(qk , $, Z) ∋ (qF , ε) ⇔ Z → $ ∈ Pk
According to previously stated ideas, automaton
f will simulate leftmost derivations consequently in
M For every i ∈ {1, . . . , k} we have according lines in
grammar G0 then G1 and so on up to Gk . Now we the δ-function. No other lines except of these are in
sketch how to construct these grammars. δ-function (i.e. for all other combinations of state, in-
put and pushdown symbol δ-function is defined to be
1
we remind that the top of the stack is on the right empty set).
Flip pushdown automata 19
First line is used for start of the simulation in G0 . Following facts also hold.
Next two lines ensure that after each flip (i.e. ∆-step)
symbol $ is read from the input and simulation of (q0 , v0 , S0 ) ⊢∗ (q0 , ε, αR ) (7)
grammar Gi takes place. Last line ensures accepting (q0 , ε, αR ) ⊢ (q1 , ε, α) (8)
end of the whole computation in successful cases.
αR ⇒∗G1 $v1 β (9)
Essence of simulation and derivation is described in
the following Lemma. This key Lemma is obvious right β ⇒∗G1 $v3 . . . $v2l−1 $v2l
R
$ . . . $v2R $ (10)
from the construction of Mf. Simulation of context free
grammar within pushdown automaton is idea that was Reasons for this are as follows. Fact (7) is due to (5)
mentioned already a few times but we refer unfamiliar and Lemma 4. Fact (8) is just ∆-step in automaton M f
reader (once more) to [4]. – construction of M f allows this transition. Facts (9)
and (10) are implied by (6) and Lemma 3.
Lemma 4. Let M f be constructed from grammars By (10) and Lemma 3, β R ⇒∗G2 $v2 γ and γ ⇒∗G2
R
G0 , . . . , Gk in the way just described. Then the follow- $v4 $ . . . $v2l $v2l−1 $ . . . $v3R $ for some nonterminal
ing equivalence holds for every v ∈ Σ ∗ and α, β ∈ Γ ∗ . word γ. This means together with (5), (9) and
Lemma 4 that (q0 , v0 , S0 ) ⊢∗ (q0 , ε, αR ), (q1 , $v1 , α) ⊢∗
(q0 , v, S0 ) ⊢∗ (q0 , ε, αR ) ⇔ S0 ⇒∗G0 vα f can
(q1 , ε, β R ) and (q2 , $v2 , β) ⊢∗ (q2 , ε, γ R ). Since M
(qi , $v, αR ) ⊢∗ (qi , ε, β R ) ⇔ α ⇒∗Gi $vβ flip the stack just before reading $ (see construction of
M above), then we get (q0 , v0 $v1 $v2 , S0 ) ⊢∗ (q2 , ε, γ R ).
(qk , $v$, αR ) ⊢∗ (qF , ε, ε) ⇔ α ⇒∗Gk $v$ Generalizing this approach – using the idea that the
derivation of w0 in G0 yields some (sub)derivations
Here i ∈ {1, . . . , k − 1} and all ⊢ transitions are by of v0 in G0 , $v1 in G1 , $v2 in G2 and so on up to
means of δ-function (i.e. without any pushdown rever- $vk in Gk (see (5), (9), see above, . . . ), we can con-
sal). f
struct (by Lemma 4) an accepting computation of M
on wk = v0 $v1 $v2 . . . $vk $. Hence Lk ⊆ T=k (M ) (re- f
Proof. Is really straightforward because δ-function
contains all transitions needed for proper simulation call the assumption wk ∈ Lk , see above).
of the leftmost derivation in grammar Gi . Formally,
f) ⊆ Lk :
T=k (M
everything would be done by induction on the length
of the leftmost derivation (or number of ⊢ steps). ⊓⊔
Lemmas 4 and 3 will be now used in reverse direction:
Theorem 2. Automaton M f does not use ε-moves from existence of accepting computation we will con-
clude that some derivations in grammars Gk , Gk−1 ,
and accepts language Lk by final state and by exactly
. . . , G0 exist. We will also use induction.
k flips.
Assume that wk = v0 $v1 . . . $vk−1 $vk $ belongs to
T f f
=k (M ). From construction of M we know that wk
f does
Proof. It is immediate from construction that M
f simulates has to be of this form – after each flip symbol $ must
not use ε-moves because all grammars M
be read, exactly k flips have to be done and this kind
are in Greibach normal form. So every production is f)
of argumentation (based only on construction of M
of the form Ni → ΣNi∗ for some i. Simulating this
f reads symbol from input. imply these statements:
production M
Now we have to prove two inclusions. We prove the (q0 , v0 $v1 $ . . . $vk $, S0 ) ⊢∗ (q0 , u1 , α1R )
more apparent one first. We assume for simplicity that
(qi , ui+1 , αi+1R
) ⊢ (qi+1 , ui+1 , αi+1 ) (11)
k = 2l. The proof is similar for k = 2l + 1.
(qi , ui , αi ) ⊢∗ (qi , ui+1 , αi+1
R
) (12)
Lk ⊆ T=k (M f) :
(qk , uk , αk ) ⊢∗ (qF , ε, ε) (13)
Assume that wk is in Lk . By Lemma 2 we know that
w0 belongs to L0 , generated by grammar G0 . This Here ui = $vi $ . . . $vk $, 1 ≤ i ≤ k. This is just com-
putation of Mf written in convenient way, assuming
means that there exists some leftmost derivation of f). Fact (11) is just pushdown rever-
w0 in grammar G0 . According to previously defined that wk ∈ T=k (M
notation we have: sal, (12) is part of computation between i-th and
i + 1-th flip and (13) is the final part of accepting
S0 ⇒∗G0 v0 $v2 $ . . . $v2l $v2l−1
R
$ . . . $v1R $ = w0 computation. We want to show that some derivation
R
of word w0 = v0 $v2 $ . . . $vk $ vk−1 $ . . . $v1R $ in gram-
S0 ⇒∗G0 v0 α (5) mar G exists, i.e. w is in L . This and Lemma 2 will
0 0 0
α ⇒∗G0 $v2 $ . . . $v2l $v2l−1
R
$ . . . $v1R $ (6) imply that wk belongs to Lk .
20 Pavol Ďuriš, Marek Košta
From assumption (13) and Lemma 4 we can infer 3.3 Summary of the proof
that
αkR ⇒∗Gk uk = $vk $ (14) Our proof consists of five main steps, we review them
here.
Fact (12) for i = k − 1 and second equivalence of
Lemma 4 lead to 1. Language L is given, accepted by automaton M ,
R
αk−1 ⇒∗Gk−1 $vk−1 αk (15) ε-steps are allowed.
2. Marks are inserted into L to denote that flip took
Facts (14) and (15) with Lemma 3 imply that place in computation. This gives us language Lk
R ∗
αk−1 ⇒Gk−1 $vk−1 $vk $R
(16) accepted by M ′ .
3. By means of flip-pushdown input-reversal tech-
Ideas contained in these statments can be transformed nique languages Lk−1 , . . . , L1 , L0 are constructed.
into formal inductive proof of the fact that in gram- Correspondence between words in Lk and L0 is
mar G0 word w0 can be derived. Main idea is that proved.
from facts like (14) and (15) we can infer (16). So 4. Automaton M f is constructed. It simulates suitable
from existence of particular part of computation one Greibach normal form grammars. M f doesn’t use
can infer that corresponding partial derivation exists. ε-steps and accepts language Lk .
These partial derivations are then joined inductively 5. Marks are deleted from language Lk yielding lan-
to form derivation of word w0 in grammar G0 . Some guage L accepted by M̄ . Well-known trick of join-
“descent” from grammar Gk to grammar Gk−1 is also ing two steps into one is used to achieve this.
important in the whole argument. We will not elab-
orate statements in fully formal way but provide one
specific example to demonstrate these ideas. 4 Closure properties
Example for k = 2. In this case w2 = v0 $v1 $v2 $. Parts In this section we establish some closure properties of
of accepting computation look like this: deterministic flip-pushdown automata. A determinis-
∗ tic flip-pushdown automaton (DFPDA) is nondeter-
(q0 , v0 , S0 ) ⊢ (q0 , ε, α1 )
R
ministic flip-pushdown automaton which has at most
(q1 , $v1 $, α1 ) ⊢∗ (q1 , ε, α2R )
one choice of action for any possible configuration.
(q2 , $v2 $, α2 ) ⊢∗ (qF , ε, ε) This means that there must never be a choice of us-
These parts of computation with Lemma 4 give us: ing an input symbol, using ε-step or ∆-step. Formally,
a flip-pushdown automaton A = (Q,Σ,Γ,δ,∆, q0 , Z0 , F )
S0 ⇒∗G0 v0 α1 is deterministic if these conditions are satisfied for all
α1R ⇒∗G1 $v1 α2 a ∈ Σ ∪ {ε}, q ∈ Q, Z ∈ Γ
α2R ⇒∗G2 $v2 $ 1. |δ(q, a, Z)| ≤ 1
These facts with Lemma 3 lead to: 2. If δ(q, ε, Z) ̸= ∅ then δ(q, a, Z) = ∅.
3. |∆(q)| ≤ 1
α2 ⇒∗G1 $v2R $ 4. If ∆(q) ̸= ∅ then δ(q, a, Z) = ∅.
α1R ⇒∗G1 $v1 $v2R $
For deterministic flip-pushdown automaton we can
α1 ⇒∗G0 $v2 $v1R $ naturally define acceptance by final state, empty push-
S0 ⇒∗G0 v0 $v2 $v1R $ = w0 down, by exactly k flips or at most k flips. We will use
notation as in previous parts, i.e. T≤k (A) or N=k (A)
⊓
⊔ with obvious meaning. Classes of languages are defined
So now we have automaton M f, accepting lan- without confusion. For example, L (DFPDA(≤ k))
guage Lk which does not use ε-moves. The final step in is class of languages accepted by deterministic flip-
our proof is to delete marks (i.e. symbols $) from Lk , pushdown automata by final state and by at most k
thus obtaining language L. Deletion of marks must be pushdown reversals. Note that some nuances are asso-
done without using ε-steps. This is easy in principle, ciated with deterministic variant of the model. Accep-
but technical. One symbol can be easily deleted with- tance by final state is not equivalent to acceptance by
out using ε-steps. Idea is quite easy: join two steps into empty pushdown for example. We refer to [1] where
one. This is standard well-known construction. Con- results concerning these questions can be found. We
stant number of symbols can be deleted by iterating will explicitly state which mode of acceptance we are
this construction. So by applying this construction on considering.
automaton M f repeatedly k-times we get the desired The following result will be of great importance for
automaton M̄ that accepts language L. us.
Flip pushdown automata 21
Theorem 3 ([2]). Language Informally, our construction did this. Take two copies
of automaton A, in second copy use symbol c instead of
Labc = {an bn cn | n ≥ 1} symbol b when reading input. Then there is an ε-step
is not accepted by any nondeterministic flip-pushdown from accepting states of first copy into corresponding
automaton. This means that Labc ∈/ L (NFPDA(fin)). accepting states of second copy. Initial state is in first
copy (identical with that of A).
Separation of hierachy is also one of the interesting How does the language T≤k (B) look like? Automa-
results which was achieved. ton B could end accepting computation in some
Theorem 4 ([2, 1]). Let k be natural number greater state qF in first copy, or in qF in second copy. First
than zero. Consider language case is not really interesting: from construction of B it
is obvious that words which caused this computation
Jk = {w1 $w1 $w2 $w2 $ . . . $wk $wk $ | are exactly those in T≤k (A) = L1 ∪ L2 .
wi ∈ {a, b}∗ , 1 ≤ i ≤ k}. Second case is the interesting one. B ended in qF ,
so one ε-step from first to second copy must have taken
Then
place. Consider time when B did this step. By con-
Jk ∈ L (DFPDA(= k)) ⊂ struction, B is at this time in a configuration in which
⊂ L (DFPDA(≤ k)) ⊂ L (NFPDA(= k)), A accepts, so input word already read at this time
must be one of an bn or an b2n for some n. When the
Jk ∈
/ L (NFPDA(= k − 1)). input word already read is an bn , then B is capable
Our next result is quite interesting. In principle it to accept an bn cn , since an bn is a prefix of an b2n ac-
says that one nondeterministic step of standard push- cepted by A, and after ε-step, B works as the second
down automaton cannot be simulated by any finite copy of A, where the symbol b is replaced by c. Simi-
number of pushdown reversals with deterministic flip- larly, when the input word already read is an b2n then
pushdown automaton. B cannot accept any word of the form an b2n v for any
v ̸= ε, since otherwise A has to accept an b2n v ′ , where
Theorem 5. L (DFPDA(≤ k) is not closed under v ′ ̸= ε is obtained from v by replacing symbols c by b,
union for any k ≥ 0. but A (recognizing L1 ∪ L2 ) cannot accept any such
Proof. Consider languages word an b2n v ′ .
Automaton A accepts L1 ∪ L2 by at most k-flips
L1 = {an bn | n ≥ 1} ∈ L (DFPDA(≤ k)), so B accepts mentioned words by at most 2k-flips (in
L2 = {an b2n | n ≥ 1} ∈ L (DFPDA(≤ k)). each copy at most k flips took place).
Consequently, we have that
These are simple deterministic pushdown languages.
We will prove by contradiction that L1 ∪ L2 does not T≤2k (B) = {an bn | n ≥ 1} ∪
belong to L (DFPDA(≤ k)) for any k. Suppose that ∪ {an b2n | n ≥ 1} ∪ {an bn cn | n ≥ 1}.
this is not the case. So deterministic flip-pushdown au-
tomaton A = (Q, {a, b}, Γ, δ, ∆, q0 , Z0 , F ) exists such Intersection with regular language a+ b+ c+ leads to
that T≤k (A) = L1 ∪ L2 . From A we will construct language Labc . This is the desired contradiction with
another nondeterministic flip-pushdown automaton B Theorem 3, since one can easily observe that
which will accept the language T≤2k (B) such that L (NFPDA(≤ l)) is closed under intersection with reg-
T≤2k (B) ∩ a+ b+ c+ = Labc . This contradiction with ular set for every l. ⊔
⊓
Theorem 3 will conclude the proof.
We construct B = (Q ∪ Q, {a, b, c}, Γ , δB , ∆B , q0 , Proposition 1. L (DFPDA(≤ k)) is closed under
Z0 , F ∪ F ) from A as follows. intersection with regular set, complement and inverse
homomorphism for every k ≥ 0.
Q = {q | q ∈ Q}
F = {q | q ∈ F } Proof. Trivial simulation of finite automaton will give
us closure under intersection with regular set.
δB (q, a, Z) ∋ (p, β) ⇔ δ(q, a, Z) ∋ (p, β)
Closure under inverse homomorphism is done via
δB (q, b, Z) ∋ (p, β) ⇔ δ(q, b, Z) ∋ (p, β) standard construction. Automaton reads input, on this
δB (q, a, Z) ∋ (p, β) ⇔ δ(q, a, Z) ∋ (p, β) homomorphism is applied and simulation takes place
δB (q, c, Z) ∋ (p, β) ⇔ δ(q, b, Z) ∋ (p, β) from buffer.
Complement is more peculiar. We give here just
δB (q, ε, Z) ∋ (q, Z) ⇔ q ∈ F
sketch of the proof. Idea is the same as with stan-
∆B (q) = ∆(q) dard deterministic pushdown automata [4]. First we
∆B (q) = {p | p ∈ ∆(q)} must ensure that automaton reads its whole input.
22 Pavol Ďuriš, Marek Košta
Here there are two main problems – automaton stucks shown that this is not the case when left quotient is
during computation because of undefined transition considered but we were unable to investigate right
or in infinite sequence of ε-moves. The first problem quotient deeper. We tried to generalize the idea of
is handled easily. Problem of looping is the main part predicting machine from deterministic pushdown
of the proof. Crucial here is that deterministic flip- automata, but without success.
pushdown automaton uses only constant number of 2. What do we get when we apply flip-pushdown
flips. After each flip detection of looping on empty in- input-reversal technique on deterministic k-flip
put can be done by mentioned technique. From these pushdown automaton? Do we get deterministic
two facts it can be inferred that detection of infinite k − 1-flip pushdown language? Or does there exist
loops can be done effectively. some other similar technique which can be used
When this normal form is achieved, construction is for deterministic variant?
quite simple. We repeatedly refer reader to [4]. ⊓
⊔ 3. Can number of states in nondeterministic k-flip
pushdown automaton be bounded without affect-
Proposition 2. L (DFPDA(≤ k)) is not closed un- ing the computational power? In pushdown au-
der intersection, homomorphism (even non-erasing), tomata normal form with one state can be
reverse, contatenation and (positive) iteration for any achieved. Our construction from section 3 yields
k ≥ 0. normal form with at most O(k) states, where k is
number of flips. Is this boundary tight?
Proof. For intersection it suffices to use De Morgan’s
4. What properties “pushdown language” Lp has?
laws, Theorem 5 and Proposition 1.
For concatenation and iteration it suffices to con- Lp = {α ∈ Γ ∗ | (q0 , w, α) ⊢∗ (q, ε, ε)}
sider language Jk and Theorem 4.
For homomorphism just take language for some w ∈ Σ ∗ and q ∈ Q. This language of
words which can be erased from pushdown
L = {can−1 bn | n ≥ 1} ∪ by some input word is regular when one considers
∪ {dan−1 b2n | n ≥ 1} standard pushdown automaton. What we can say
about it here?
and homomorphism h(a) = h(c) = h(d) = a, h(b) = b. 5. Which properties are decidable? This is only in-
Apply h and use Theorem 5. teresting when deterministic variant is considered
For reverse just apply construction from Theorem 5 because for nondeterministic variant these results
on language LR where can be derived from previous work easily. We high-
light two non-trivial properties about determinis-
L = d{b2n an | n ≥ 1} ∪ {bn an | n ≥ 1}. tic flip-pushdown automata which are not easily
implied by previous results. These are: regularity
This construction will give us nondeterministic flip-
problem and equality problem. Are these decid-
pushdown automaton accepting language
able?
L′ = {an bn | n ≥ 1} ∪
∪ {an b2n | n ≥ 1}d ∪ {an bn cn d | n ≥ 1}. References
But this also leads to contradiction with Theorem 3. 1. M. Holzer and M. Kutrib: Flip-pushdown automata:
⊓
⊔ nondeterminism is better than determinism. LNCS
2710, 2003, 361–372.
2. M. Holzer and M. Kutrib: Flip-pushdown automata:
5 Conclusions k + 1 pushdown reversals are better than k. LNCS 2719,
2003, 490–501.
We discussed flip-pushdown automaton model. Our 3. P. Sarkar: Pushdown automaton with the ability to flip
main contribution to this area of theoretical research its stack. ECCC Report No. 81, 2001.
is solution of problem of ε-moves. We proved that 4. J.E. Hopcroft and J.D. Ullman: Introduction to au-
ε-moves can be removed and normal form effectively tomata theory, languages and computation. Addison-
achieved. Some (non)closure properties of determinis- Wesley, 1979.
5. S.A. Greibach: A new normal-form theorem for context-
tic model were also investigated. Our results answer
free phrase structure grammars. Journal of ACM 12,
some open questions formulated in [1]. Finally, we list
1965, 42–52.
some interesting questions which wait for answer.
1. Is L (DFPDA(≤ k)) closed under right quotient
with regular set? From our results it can be easily