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