Flip-pushdown automaton is pushdown automaton which has ability to flip its pushdown throughout the computation. This model was introduced in [3] by Sarkar. Here we solve in the affirmative the following open problem posed by Holzer and Kutrib in [1]: What is the power of "-moves for nondeterministic flip-pushdown automata - can they be removed without affecting the computational capacity? (" denotes the empty word.) Moreover, we prove here that the family of languages recognized by the deterministic variant of the flip-pushdown automata (with k-pushdown reversals) is closed under intersection with regular sets, complement and inverse homomorphism, but it is not closed under union, intersection, (non-erasing) homomorphism, reverse, concatenation and (positive) iteration. Finally, we formulate some new questions and pose new problems.
The problem we deal with is the power of ε-moves.
Well-known and famous result by Greibach [5] is the so-called Greibach normal form for the context-free grammar. With this result one can easily prove that for every pushdown automaton ε-free pushdown automaton can be constructed. By ε-free pushdown automaton we mean automaton that does not use ε-moves.
Our main result parallels this nicely: for every flippushdown automaton other ε-free flip-pushdown automaton accepting the same language can be found.
Moreover, our proof of this fact is constructive. Of course we will use Greibach normal form quite extensively.
In section 2 we give necessary formal definitions 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 without affecting computational power of the nondeterministic flip-pushdown automaton model. Some closure properties of families of languages described by deterministic flip-pushdown automata are discussed in section 4. Finally, we summarize our results and pose new problems in section 5. ⋆ 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 fliping". pushdown automaton A is in configuration (q, w, γ), 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 automasibilities 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 = {wvR 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 acstandard 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, automaautomaton has two possibilities in any configuration: ton M ′ can be effectively constructed from automaeither apply δ-function or apply ∆-function. Nonde- ton M and vice versa. terministic choice is made to choose the next configuration. 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 acmeaning 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 connecby 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 pushempty 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 cTl≤akss(Aco)n=taLi)niinsgdeanllottehdesbeycLlas(sNesFiPs DA(≤ k)). Broader 3.1 Main idea ∞ 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 = v0v1 . . . 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 De nition 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”, see Theorem 1. So Li is accepted by some i-flip pushHere α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 derivaIn the following we assume for simplicity that We will use the concept of reverse grammar extenk = 2l, case when k = 2k + 1 is proved similarly. We sively in the following so here is formal definition. two following Lemmas.
Lemma 1. Let Lk be the previously defined language.
Let Lk, . . . , L0 be the languages, where the language of Theorem 1 for 1 ≤ i ≤ k. Then word w = Li−1 is obtained from language Li by one application
v0$v1$ . . . $vi−1$vi$vi+1$ . . . $vk−1$vk$ is in language Li if and only if word w′ =
v0$v1$ . . . $vi−1$vkR$vkR−1$ . . . $viR+1$viR$ is in language Li−1 for 1 ≤ i ≤ k.
Proof. Quite obvious. The last flip in computation on word w occurs after subword vi. Because symbol $ is new and also from formulation of Theorem 1 stated correspondence between words from Li and Li−1 holds.
Lemma 2. When k = 2l then word w0 =
v0$v2$ . . . $v2l$v2Rl−1$ . . . $v3R$v1R$ belongs to language L0 if and only if word wk = v0$v1$ . . . $vk$ belongs to Lk. In case k = 2l + 1 words in L0 have form
v0$v2$ . . . $v2l$v2Rl+1$v2Rl−1$ . . . $v3R$v1R$ Proof. Just apply Lemma 1 inductively k times. will exploit correspondence between words in L0 and those in Lk stated in Lemma 2. Language L0 is by definition context-free so there is Greibach normal form context free grammar generating it. We want to simulate leftmost derivations in this grammar (and others constructed from this one) with flip-pushdown automaton. this:
Let us have context-free grammar
G0 = (N0, Σ ∪ {$}, P0, S0), such that L(G0) = L0. Leftmost derivation of word w0 ∈ L0 in grammar G0 looks like
S0 ⇒∗ v0α0 ⇒
∗ ⇒∗ v0$v2α2 ⇒ ∗ v0$v2$v4α4 ⇒
∗ ⇒∗ v0$v2$v4 . . . $v2lα2l ⇒
∗ ⇒∗ v0$v2$v4 . . . $v2l$v2Rl−1α2l−1 ⇒
∗ ⇒∗ v0$v2$v4 . . . $v2l$v2Rl−1$v2Rl−3α2l−3 ⇒
∗ ⇒∗ · · · ⇒
∗
⇒∗ v0$v2$v4 . . . $v2l$v2Rl−1$ . . . $v3R$v1R$ = w0
tion in right way we could obtain “derivation” of word
wk instead of w0 (w0 and wk are from Lemma 2). This
means that if we could after (
S0 ⇒∗G0 v0α0 reverse nonterminal string
v0α0R now continue in G1
⇒∗G1 v0$v1β β is nonterminal string in G1
The main idea of the previous process is this. We want
to simulate the leftmost derivation (in grammar G0)
by pushdown automaton, storing nonterminal string
on the stack. When reversal takes place, automaton
will simulate leftmost derivation in G1 (we will call it
reverse grammar) and so on. By continuing this
simulation in suitable grammars making reversals along
the way we can obtain valid accepting computation
on word wk. Deeper analysis will follow but first we
need some notation based on (
= = = = α0 u u u R Ai ⇒∗G0 xi ∈ T ∗
A1 . . . An x1 . . . xn $v2$v4 . . . $v2l$v2Rl−1$ . . . $v3R$v1R$ $v1$v3$ . . . $v2l−1$v2Rl$ . . . $v4R$v2R$ De nition 3. We say that context-free grammar H = (NH , T, PH , SH ) is reverse grammar to context-free grammar I = (NI , T, PI , SI ) if the following conditions hold: 1. H is in Greibach normal form 2. NH ∩ NI = NI 3. (∀ξ ∈ NI )(∀z ∈ T ∗) ξ ⇒∗H zR ⇐⇒
ξ ⇒I∗ z Lemma 3. Assume that H is reverse grammar to I.
Then for every α (non-empty nonterminal string of grammar I) and v (terminal string) we have: α ⇒I∗ v if and only if αR ⇒∗H v
R Proof. Easy induction on the length of α. From definition 3 we see that the statement holds when |α| = 1.
Assume that the statement hold for all α of length k. definition 3 this is equivalent to AαR Now let αA ⇒I∗ v vA. By induction hypothesis and
⇒∗H vARvR. So
the statement of the Lemma follows by induction.
⊔⊓
⊔⊓
(
$v1$v3$ . . . $v2l−1$v2Rl$ . . . $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 definition is a little bit cumbersome. Our idea is to repAn . . . A1 ⇒∗G1 $v1B1B2 . . . Bm resent sentential form on the stack and do computation with this representation (doing flips and simulate where Bi are nonterminals of grammar G1. So Mf 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 simplicBm . . . 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 pushsimulating 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 Mf will not use ε-moves when simulating these symbol must be at the bottom of the stack. So sentengrammars. tial form is represented “as is” on the stack. Let Mf = (Q, Σ ∪ {$}, Γ , δ, ∆, q0, S0, {qF }), where 3.2
Q = {q0, q1, . . . , qk} ∪ {q1, . . . , qk} ∪ {qF }, Σ is alphabet of M ′ and $ is new symbol, 1 we remind that the top of the stack is on the right So we have M ′ accepting language Lk (see the beginning of subsection 3.1) by empty pushdown and by exactly k flips. By Lemma 2, L0 can be generated by ∆(qi) = {qi+1} ∧ 0 ≤ i ≤ k − 1. some context-free grammar G0 = (N0, Σ, P0, S0). Standard pushdown moves (i.e. δ-steps) will ensure the We want to construct automaton Mf 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 special than this: from construction it will be appar- δ(q0, a, S0) ∋ (q0, βR) ⇔ a ∈ Σ ∧ S0 → aβ ∈ P0 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 Mf will simulate leftmost derivations consequently in grammar G0 then G1 and so on up to Gk. Now we sketch how to construct these grammars.
For every i ∈ {1, . . . , k} we have according lines in the δ-function. No other lines except of these are in δ-function (i.e. for all other combinations of state, input and pushdown symbol δ-function is defined to be empty set).
Γ = {A | where A is nontermial of Gi, 0 ≤ i ≤ k}, First line is used for start of the simulation in G0. Following facts also hold. (7) (8) (9) Next two lines ensure that after each flip (i.e. ∆-step) symbol $ is read from the input and simulation of grammar Gi takes place. Last line ensures accepting end of the whole computation in successful cases.
Essence of simulation and derivation is described in the following Lemma. This key Lemma is obvious right from the construction of Mf. Simulation of context free grammar within pushdown automaton is idea that was mentioned already a few times but we refer unfamiliar reader (once more) to [4].
f be constructed from grammars G0, . . . , Gk in the way just described. Then the following equivalence holds for every v ∈ Σ∗ and α, β ∈ Γ ∗. (q0, v, S0) ⊢∗ (q0, ε, αR) ⇔ S0 ⇒∗G0 vα (qi, $v, αR) ⊢∗ (qi, ε, βR) ⇔ α ⇒Gi $vβ ∗ (qk, $v$, αR) ⊢∗ (qF , ε, ε) ⇔ α ⇒∗Gk $v$ Here i ∈ {1, . . . , k − 1
} and all ⊢ transitions are by means of δ-function (i.e. without any pushdown reversal).
Proof. Is really straightforward because δ-function contains all transitions needed for proper simulation of the leftmost derivation in grammar Gi. Formally, everything would be done by induction on the length of the leftmost derivation (or number of ⊢ steps). ⊔⊓
does not use ε-moves and accepts language Lk by final state and by exactly k flips. not use ε-moves because all grammars M Proof. It is immediate from construction that Mf does f simulates are in Greibach normal form. So every production is of the form Ni → ΣNi∗ for some i. Simulating this production Mf reads symbol from input.
Now we have to prove two inclusions. We prove the more apparent one first. We assume for simplicity that k = 2l. The proof is similar for k = 2l + 1.
Lk ⊆ T=k(Mf) : Assume that wk is in Lk. By Lemma 2 we know that w0 belongs to L0, generated by grammar G0. This means that there exists some leftmost derivation of w0 in grammar G0. According to previously defined notation we have:
S0 ⇒∗G0 v0$v2$ . . . $v2l$v2Rl−1$ . . . $v1R$ = w0 S0 ⇒∗G0 v0α α ⇒∗G0 $v2$ . . . $v2l$v2Rl−1$ . . . $v1R$ (q0, v0, S0) ⊢ (q0, ε, αR) ⊢ ∗ (q0, ε, αR)
(q1, ε, α) αR
⇒∗G1 $v1β
β ⇒∗G1 $v3 . . . $v2l−1$v2Rl$ . . . $v2R$ (10)
Reasons for this are as follows. Fact (7) is due to (
By (10) and Lemma 3, βR $v4$ . . . $v2l$v2Rl−1$ . . . $v3R$ for ⇒∗G2
$v2γ and γ ⇒∗G2 some nonterminal word γ.
means
together
with (
Assume that wk = v0$v1 . . . $vk−1$vk$ belongs to
T=k(Mf). From construction of Mf
we know that wk
has to be of this form – after each flip symbol $ must
be read, exactly k flips have to be done and this kind
of argumentation (based only on construction of Mf)
(q0, v0$v1$ . . . $vk$, S0) ⊢∗ (q0, u1, α1R)
(qi, ui+1, αiR+1) ⊢ (qi+1, ui+1, αi+1) (11)
(qi, ui, αi) ⊢∗ (qi, ui+1, αiR+1)
(qk, uk, αk) ⊢∗ (qF , ε, ε)
(12)
(13)
(
putation of Mf Here ui = $vi$ . . . $vk$, 1 ≤ i ≤ k. This is just comwritten in convenient way, assuming sal, (12) is part of computation between i-th that wk ∈ T=k(Mf). Fact (11) is just pushdown reverand i + 1-th flip and (13) is the final part of accepting computation. We want to show that some derivation of word w0 = v0 $v2$ . . . $vk$ vkR−1$ . . . $v1R$ in grammar G0 exists, i.e. w0 is in L0. This and Lemma 2 will that αR
k ⇒∗Gk uk = $vk$
Fact (12) for i = k − 1 and second equivalence of From assumption (13) and Lemma 4 we can infer 3.3
Facts (14) and (15) with Lemma 3 imply that αkR−1 ⇒Gk 1 ∗
$vk−1αk αkR−1 ⇒Gk 1 ∗ $vk−1$vkR$ Ideas contained in these statments can be transformed into formal inductive proof of the fact that in grammar G0 word w0 can be derived. Main idea is that from facts like (14) and (15) we can infer (16). So from existence of particular part of computation one can infer that corresponding partial derivation exists. These partial derivations are then joined inductively to form derivation of word w0 in grammar G0. Some “descent” from grammar Gk to grammar Gk−1 is also important in the whole argument. We will not elaborate statements in fully formal way but provide one specific example to demonstrate these ideas. (14) (15) (16) ⊔⊓
Our proof consists of five main steps, we review them here. 1. Language L is given, accepted by automaton M , ε-steps are allowed.
accepted by M ′. 2. Marks are inserted into L to denote that flip took place in computation. This gives us language Lk 3. By means of flip-pushdown input-reversal technique languages Lk−1, . . . , L1, L0 are constructed. Correspondence between words in Lk and L0 is proved.
ε-steps and accepts language Lk. 4. Automaton Mf is constructed. It simulates suitable
Greibach normal form grammars. Mf doesn’t use 5. Marks are deleted from language Lk yielding language L accepted by M¯ . Well-known trick of joining two steps into one is used to achieve this. 4
Closure properties deterministic flip-pushdown automata. A deterministic flip-pushdown automaton (DFPDA) is nondeterministic flip-pushdown automaton which has at most one choice of action for any possible configuration. This means that there must never be a choice of using an input symbol, using ε-step or ∆-step. Formally, a flip-pushdown automaton A = (Q,Σ,Γ,δ,∆, q0, Z0, F ) is deterministic if these conditions are satisfied for all a ∈ Σ ∪ {ε}, q ∈ Q, Z ∈ Γ 1. |δ(q, a, Z)| ≤ 1 2. If δ(q, ε, Z) ̸= ∅ then δ(q, a, Z) = ∅. 3. |∆(q)| ≤ 1 4. If ∆(q) ̸= ∅ then δ(q, a, Z) = ∅.
For deterministic flip-pushdown automaton we can naturally define acceptance by final state, empty pushdown, 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 without confusion. For example, L (DFPDA(≤ is class of languages accepted by deterministic flipk)) pushdown automata by final state and by at most k pushdown reversals. Note that some nuances are assoSo now we have automaton Mf, accepting language Lk which does not use ε-moves. The final step in our proof is to delete marks (i.e. symbols $) from Lk, thus obtaining language L. Deletion of marks must be done without using ε-steps. This is easy in principle, ciated with deterministic variant of the model. Accepbut technical. One symbol can be easily deleted withtance 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. Conresults 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¯ that accepts language L. automaton Mf repeatedly k-times we get the desired us.
The following result will be of great importance for These parts of computation with Lemma 4 give us:
of accepting computation look like this: Example for k = 2. In this case w2 = v0$v1$v2$. Parts In this section we establish some closure properties of (q0, v0, S0) ⊢∗ (q0, ε, α1R) (q1, $v1$, α1) ⊢∗ (q1, ε, α2R) (q2, $v2$, α2) ⊢∗ (qF , ε, ε)
S0 ⇒∗G0 v0α1 αR
1 ⇒∗G1 $v1α2 αR
2 ⇒∗G2 $v2$ α2 ⇒∗G1 $v2R$ αR 1 ⇒∗G1 $v1$v2R$ α1 ⇒∗G0 $v2$v1R$ S0 ⇒∗G0 v0$v2$v1R$ = w0 Theorem 3 ([2]). Language Informally, our construction did this. Take two copies
Labc = {anbncn | n ≥ 1} soyf maubtoolmbawtohnenA,reinadsiencgonindpcuotp.yTuhseensytmhebroelics iannstεe-asdteopf 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? Automaresults 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 , Then spolaocnee. εC-ostnespidferromti mfirestwthoesnecBonddicdoptyhimsusstteph.avBeytackoennJk ∈ 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 anbn or anb2n for some n. When the Jk ∈/ L (NFPDA(= k − 1)). input word already read is anbn, then B is capable Our next result is quite interesting. In principle it to accept anbncn, since anbn is a prefix of anb2n acsays 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. Siminumber of pushdown reversals with deterministic flip- larly, when the input word already read is anb2n then pushdown automaton. B cannot accept any word of the form anb2nv for any v ̸= ε, since otherwise A has to accept anb2nv′, 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 anb2nv′.
Automaton A accepts L1 ∪ L2 by at most k-flips L1 = {anbn | n ≥ 1} ∈ L (DFPDA(≤ k)), so B accepts mentioned words by at most 2k-flips (in L2 = {anb2n | 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 belong to L (DFPDA(≤ k)) for any k. Suppose that this is not the case. So deterministic flip-pushdown automaton A = (Q, {a, b}, Γ, δ, ∆, q0, Z0, F ) exists such that T≤k(A) = L1 ∪ L2. From A we will construct another nondeterministic flip-pushdown automaton B which will accept the language T≤2k(B) such that T≤2k(B) ∩ a+b+c+ = Labc. This contradiction with Theorem 3 will conclude the proof.
We construct B = (Q ∪ Q, {a, b, c}, Γ , δB, ∆B, q0, Z0, F ∪ F ) from A as follows.
Q = {q | q ∈ Q}
F = {q | q ∈ F } δB(q, a, Z) ∋ (p, β) ⇔ δ(q, a, Z) ∋ (p, β) δB(q, b, Z) ∋ (p, β) ⇔ δ(q, b, Z) ∋ (p, β) δB(q, a, Z) ∋ (p, β) ⇔ δ(q, a, Z) ∋ (p, β) δB(q, c, Z) ∋ (p, β) ⇔ δ(q, b, Z) ∋ (p, β) δB(q, ε, Z) ∋ (q, Z) ⇔ q ∈ F ∆B(q) = ∆(q) ∆B(q) = {p | p ∈ ∆(q)}
T≤2k(B) = {anbn | n ≥ 1} ∪
∪ {anb2n | n ≥ 1} ∪ {anbncn | n ≥ 1}.
Intersection with regular language a+b+c+ leads to language Labc. This is the desired contradiction with Theorem 3, since one can easily observe that L (NFPDA(≤ l)) is closed under intersection with regular set for every l.
⊔⊓
intersection with regular set, complement and inverse homomorphism for every k ≥ 0.
Proof. Trivial simulation of finite automaton will give us closure under intersection with regular set.
Closure under inverse homomorphism is done via standard construction. Automaton reads input, on this homomorphism is applied and simulation takes place from buffer.
Complement is more peculiar. We give here just sketch of the proof. Idea is the same as with standard deterministic pushdown automata [4]. First we must ensure that automaton reads its whole input. Here there are two main problems – automaton stucks during computation because of undefined transition or in infinite sequence of ε-moves. The first problem is handled easily. Problem of looping is the main part of the proof. Crucial here is that deterministic flipflips. After each flip detection of looping on empty input can be done by mentioned technique. From these two facts it can be inferred that detection of infinite loops can be done effectively. pushdown automaton uses only constant number of 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 shown that this is not the case when left quotient is considered but we were unable to investigate right quotient deeper. We tried to generalize the idea of predicting machine from deterministic pushdown automata, but without success. input-reversal technique on deterministic k-flip pushdown automaton?
Do we get deterministic k − 1-flip pushdown language? Or does there exist some other similar technique which can be used pushdown automaton be bounded without affecting the computational power? In pushdown automata normal form with one state can achieved. Our construction from section 3 yields normal form with at most O(k) states, where k is number of flips. Is this boundary tight?
Lp = {α ∈ Γ ∗ | (q0, w, α) ⊢∗ (q, ε, ε)} for some w ∈ Σ∗ and q ∈ Q. This language of words which can be erased from pushdown by some input word is regular when one considers standard pushdown automaton. What we can say about it here? 5. Which properties are decidable? This is only interesting when deterministic variant is considered Proposition 2. L (DFPDA(≤ k)) is not closed under intersection, homomorphism (even non-erasing), reverse, contatenation and (positive) iteration for any k ≥ 0.
Proof. For intersection it suffices to use De Morgan’s laws, Theorem 5 and Proposition 1.
For concatenation and iteration it suffices to consider language Jk and Theorem 4.
L = {can−1bn | n ≥ 1} ∪ ∪ {dan−1b2n | n ≥ 1} and homomorphism h(a) = h(c) = h(d) = a, h(b) = b.
For reverse just apply construction from Theorem 5 on language LR where
L = d{b2nan | n ≥ 1} ∪ {bnan | n ≥ 1}.
This construction will give us nondeterministic flippushdown automaton accepting language
L′ = {anbn | n ≥ 1} ∪ But this also leads to contradiction with Theorem 3. 5
Conclusions 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∪ { anb2n | n ≥ 1}d ∪ {anbncnd | n ≥ 1}. ε-moves can be removed and normal form effectively achieved. Some (non)closure properties of deterministic model were also investigated. Our results answer some open questions formulated in [1]. Finally, we list 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 ⊔⊓ nondeterminism
is better than determinism. LNCS 2710, 2003, 361{372.
2003, 490{501. 2. M. Holzer and M. Kutrib: Flip-pushdown