Pushdown Automata

10 Key excerpts on "Pushdown Automata"

• 

  eBook - PDF

  Formal Languages and Computation

  Models and Their Applications

  • Alexander Meduna(Author)
  • 2014(Publication Date)
  • Auerbach Publications

    (Publisher)

  Models for Context-Free Languages ◾ 113 6.3 Pushdown Automata In essence, a pushdown automaton is an FA extended by a potentially infinite stack, commonly referred to as a pushdown list or, briefly, a pushdown� The present section demonstrates that a lan-guage is context-free iff it is accepted by a pushdown automaton� It is divided into Sections 6�3�1 through 6�3�4� Section 6�3�1 defines Pushdown Automata� Section 6�3�2 establishes the equiva-lence between them and CFGs� Section 6�3�3 introduces three ways of accepting languages by these automata and shows that they all are equally powerful� Finally, Section 6�3�4 narrows its attention to the deterministic versions of Pushdown Automata and demonstrates that they are less powerful than their nondeterministic versions� 6.3.1 Pushdown Automata and Their Languages Definition 6.50 A pushdown automaton ( PDA ) is a rewriting system, M = ( Σ , R ), where ◾ Σ is divided into subalphabets Q , Γ , Δ such that Q ∩ ( Γ ∪ Δ ) = ∅ � ◾ R is a finite set of rules of the form x → y , where x ∈ Γ * Q ( Δ ∪ { ε }) and y ∈ Γ * Q � Q , Γ , and Δ are referred to as the set of states , the alphabet of pushdown symbols , and the alphabet of input symbols , respectively� Q contains the start state , denoted by s , and a set of final states , denoted by F � Γ contains the start symbol , S � If Ssw ⇒ * f in M with f ∈ F , M accepts w � The set of all strings that M accepts is the language accepted by M , denoted by L ( M )—that is, L ( M ) = { w | w ∈ Δ * , Ssw ⇒ * f , f ∈ F } Thus, according to Definition 6�50, PDAs represent special cases of rewriting systems, intro-duced in Section 2�2� We frequently make use of the terminology concerning rewriting systems introduced in Section 2�2�1 when discussing PDAs� Convention 6.51 We denote the set of all PDAs by PDA Ψ , and we set PDA Φ = { L ( M )| M ∈ PDA Ψ }� For every M ∈ PDA Ψ , a

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Theory of Computation Simplified

  Simulate Real-world Computing Machines and Problems with Strong Principles of Computation (English Edition)

  • Dr. Varsha H. Patil, Dr. Vaishali S. Pawar, Dr. Swati A. Bhavsar, Dr. Aboli H. Patil(Authors)
  • 2022(Publication Date)
  • BPB Publications

    (Publisher)

  HAPTER 6

  Push Down Automata

  After learning regular language in the previous chapter, this chapter introduces push down automata. Push down automata is a computational model that is used to solve any problem which has algorithmic solution and requires a stack memory. Having a memory, it can remember arbitrarily long input strings which are not yet processed by finite automaton. Push down automata can accept and recognize context free languages. We shall learn the use of PDA in parsing, equivalence of PDAs and CFGs, inter-conversion of CFGs and PDAs, Deterministic pushdown automaton (DPDA ) and Non-deterministic Pushdown Automata (NPDA ), and a pumping Lemma for Context Free Languages, a pumping Lemma for Context Free Languages.

  Structure

  In this chapter, we will discuss the following topics:

  • Push Down Automata
  • The language defined by Push Down Automata
  • Pictorial representation of PDA
  • Parsing and Use of PDA in parsing
  • Equivalence of PDAs and CFGs
  • Inter-conversion of CFGs and PDAs
  • Deterministic pushdown automaton (DPDA) and Non-deterministic Pushdown Automata (NPDA)
  • Multi-stack PDA
  • A pumping Lemma for Context Free Languages
  • Closure and Decision properties of context free language

  Objectives

  The objective behind learning push down automata is to learn construction of push down automata. In this chapter, we will understand construction of deterministic and non-deterministic push down automata, Convert context free grammar into push down automata, how to convert push down automata into context free grammar, how to apply pumping lemma to determine whether the language is context free or not, and closure and decision properties of context-free languages.

  6.1 Introduction

  The formal construction of PDA and its theoretical development originated from the works of A. Oettinger, Chomsky, Schut Zenburger, and Evey on formal languages theory. In the earlier chapters, we learnt a class of languages, context free languages (CFL

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Handbook of Finite State Based Models and Applications

  • Jiacun Wang(Author)
  • 2016(Publication Date)
  • Chapman and Hall/CRC

    (Publisher)

  1.5 Variants of Finite Automata 1.5.1 Pushdown Automata Pushdown Automata (PDA) are like the NFAs with control of both an input tape and a stack. The stack provides additional memory beyond the finite amount available in the control. The stack allows a PDA to recognize some nonregular languages. Given an input symbol, current state, and stack symbol, the automaton can follow a transition to another state, and optionally manipulate (push or pop) the stack. A PDA can recognize a nonregular language like { 0 n 1 n : n ≥ 0 } because it can use the stack to remember the number of 0s it has seen. 14 Handbook of Finite State Based Models and Applications A pushdown automaton (in brief a PDA) M is a 6-tuple ( Q , Σ , Γ , δ , q 0 , F ), where Σ is an input alphabet, Γ is a stack alphabet, Q is a finite set of states, q 0 ∈ Q is the initial state, F ⊆ Q is the set of accepting states, and a transition function δ : Q × ( Σ ∪ { } ) × Γ −→ P fin ( Q × Γ ∗ ), which specifies the next state as well as the stack symbols to be pushed in place of the top stack symbol. An input string w is accepted if the PDA M on processing the entire string w empties its stack. The language accepted by M is the set of all strings that it accepts. Such languages are called context-free languages . Context-free languages are also generated by context-free grammars , a finite set of rules that specifies how strings should be generated beginning from a start symbol. A typical context-free language is given by L = { ww R : w ∈ { a , b } ∗ } , where w R is the string obtained from w by reading the letters of w in the reverse order. A pushdown automaton accepting L behaves as follows. Given an input of the form ww R , the PDA pushes symbols onto the stack that correspond to the letters of the prefix w . Having guessed that it has come to the middle of the input, the symbols on the stack will now correspond to w R when read from the top.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Syntactic Methods in Pattern Recognition

  • K. S. Fu(Author)
  • 1974(Publication Date)
  • Elsevier Science

    (Publisher)

  2.4 Context-Free Languages and Pushdown Automata 35 Theorem 2.5 (Greibach normal form) Any context-free language can be generated by a grammar G = (VN, V, P, S ) in which every production is of the form A + ar with A E VN, a E V,, and CI E VN*. Theorem 2.6 (“uvwxy theorem”) Let L be any context-free language. There exist constants p and q depending only on L, such that if there is a string z in L, with IzI > p , then z may be written as z = uuwxy, where I uwxl I q and u and x are not both I., such that for each integer i 2 0, u u ’ w x ~ is in L. A context-free grammar G is said to be “self-embedding” if there is a nonterminal A with the property that A CI,ALY, where mi, at E V’. The nonterminal A is also said to be self-embedding. It is noted that the self- embedding property gives rise to sentences of the form uu’wx’y and distin- guishes a strictly context-free language from a finite-state language. If we have a context-free grammar G which is non-self-embedding, then we know that L(G) is a finite-state language. Consequently, a context-free language is non-finite state (or nonregular) if and only if all of its grammars are self-embedding. A pushdown automaton is essentially a finite-state automaton with an additional pushdown storage. The pushdown storage is a “ first-in/last out’’ stack. That is, symbols may be entered (stored) or removed (read out) only at the top of the stack. The stack of trays on a spring that is often seen in cafeterias serves as a good example of pushown storage. The spring below the trays has just enough strength so that only one tray appears above the level of the counter. When the top tray is removed, the load on the spring is lightened, and the next tray in the stack appears above the level of the counter. If a tray is put on top of the stack, the pile is pushed down, and the tray just put on appears above the counter. For our purpose, the capacity of the stack can be arbitrarily large, so that we may add as many trays as we desire.

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Automata and Computability

  A Programmer's Perspective

  • Ganesh Gopalakrishnan(Author)
  • 2019(Publication Date)
  • Chapman and Hall/CRC

    (Publisher)

  12 Pushdown Automata

  Chapter Gist: Pushdown Automata (PDA) receive an elaborate informal introduction (§12.1) followed by a formal one (§12.2). We explore a PDA for LDyck using Jove (§12.3), and follow this with in-depth descriptions of many curious executions of PDA on made-up examples (§12.4). These include stack-limited executions, and a discussion of preventing infinite-looping in Jove (§12.4.1). We then present more practical examples in the Automd markdown notation (§12.5). We discuss CFG to PDA conversion, including non-deterministic executions of PDA derived from ambiguous CFGs (§12.6). This book presents you with the opportunity to study three parsers, summarized in §12.7.

  12.1  Pushdown Automaton Basics

  Pushdown Automata (PDA) are machines that recognize the structure in the input string with the aid of a finite-state control mechanism whose actions are governed by the string as well as the contents of an unbounded stack. The stack contents are created by the PDA itself, and includes information gathered from the input seen so far and also symbols that the PDA itself puts into the stack (to “remember” or “mark” important junctures).1 As a simple example, in order to recognize strings from LDyck , a PDA can use the stack to store left parentheses, ‘(’. When right parentheses, ‘)’, arrive in the input stream, the PDA can pop the stored left parentheses and match against them.

  A PDA (Figure 12.1 ) always starts from a single initial state with input consisting of a string over Σ* to be processed on the “input tape”. PDA transitions are governed by a somewhat complex edge-label type that has the following structure:

  oneInChrOrEps , oneStackSymOrEps ; stringOfStackSyms

  Figure 12.1: A Pushdown Automaton shown with its input string and its stack. The input of a PDA is read left-to-right once. A PDA cannot rewind its read position back to an earlier point in the string and re-read an input. This is the same as with NFA. (Turing machines—discussed in Chapter 13

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Elements of Compiler Design

  • Alexander Meduna(Author)
  • 2007(Publication Date)
  • Auerbach Publications

    (Publisher)

  3.3.1 Power of Parsing Models This section briefly compares the power of grammars and Pushdown Automata, including their deterministic versions. Theorem 3.18. The Pushdown Automata and the grammars are equally powerful. Proof . In the previous section, we have constructed two parsers for any grammar. As these parsers represent special cases of Pushdown Automata, from any grammar, we can construct an equivalent pushdown automaton. We can also transform any pushdown automaton to an equivalent grammar. In reality, this transformation is obviously hardly ever needed in parsing, so we leave it as an exercise. 104 3 Syntax Analysis The deterministic versions of Pushdown Automata fulfill obviously a crucial role in parsing because they are easy to implement and apply in reality. Unfortunately, they are not as powerful as their general versions, which are as powerful as grammars by the previous theorem. Theorem 3.19. The deterministic Pushdown Automata are less powerful than the Pushdown Automata. Proof . By Definition 2.6, every deterministic pushdown automaton is a special case of a pushdown automaton. On the other hand, consider the language L = { wv | w , v ∈ {0, 1} * , v = reversal ( w )}. A pushdown automaton can accept L so it first moves w onto the pushdown. Then, it reads v and, simultaneously, compares it with the pushdown contents. In greater detail, during every move of this comparison, it verifies that the current input symbol and the pushdown top symbol coincide. If they do, the automaton pops the pushdown top symbol, reads the next input symbol, and continues by making the next comparison. If in this way, the pushdown automaton empties the pushdown and, simultaneously, reads the entire input string, it accepts. We thus intuitively see that during this process, the automaton has to non-deterministically choose the move from which it starts the comparison in a non-deterministic way.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Introduction To Formal Languages And Machine Computation, An

  • Song Y Yan(Author)
  • 1998(Publication Date)
  • World Scientific

    (Publisher)

  (iii) W = {wij)ij G Z, Wij G R is the bi-infinite connection matrix, satisfying Vx = (x l ) ie z G £ Z and Vi G Z = > ^WijXj is convergent. (2.35) j (iv) £ G R z is the threshold vector. (iv) 5i is the activation junction of neuron z, defined by 6 l : R -> S. (2.36) We refer interested readers to [24] and [45] for more information about cellular automata and neural-like cellular automata. 2.3 Push-Down Automata and Context-Free Languages Push-Down Automata (PDA) form the most important class of automata be-tween finite automata and Turing machines. As we have seen from the previous section, DFAs cannot accept even very simple languages such as {x n y n : n G N}, but fortunately, there exists a more powerful machine, push-down automata, which can accept it. Just as DFA and NFA, there are also two types of push-down automata: Deterministic Push-Down Automata (DPDA) and Non-Deterministic Push-Down Automata (NPDA). The languages which can be ac-cepted by PDA are called Context-Free Languages (CFL), denoted by LQF-Diagrammatically, a PDA is a finite state automaton (see Figure 2.12), with memories (push-down stacks). In this section, we shall study push-down au-tomata (PDA) and their associated languages, context-free languages LQF- 2.3. Push-Down Automata and Context-Free Languages 129 Input File Fite State Control Unit Stack Figure 2.12: Push-Down Automata 2.3.1 Push-Down Automata (PDA) We first give a formal definition of non-deterministic push-down automata (NPDA). Definition 2.3.1 A Non-deterministic Push-Down Automata (NPDA) is de-fined by M = (Q,£,r, finite subsets of Q x P (2.38) (v) z G T is the stack initial symbol,

  Sign up to read

  Learn more about book
• 

  No longer available |Learn more

  Introduction to Theory of Computation, An

  • (Author)
  • 2014(Publication Date)
  • Learning Press

    (Publisher)

  This kind of automaton is called a pushdown automaton Transition function • Deterministic : For a given current state and an input symbol, if an automaton can only jump to one and only one state then it is a deterministic automaton . • Nondeterministic : An automaton that, after reading an input symbol, may jump into any of a number of states, as licensed by its transition relation. Notice that the term transition function is replaced by transition relation: The automaton non-deterministically decides to jump into one of the allowed choices. Such automaton are called nondeterministic automaton . • Alternation : This idea is quite similar to tree automaton, but orthogonal. The automaton may run its multiple copies on the same next read symbol. Such automata are called alternating automaton . Acceptance condition must satisfy all runs of such copies to accept the input. Acceptance condition • Acceptance of finite words : Same as described in the informal definition above. • Acceptance of infinite words : an omega automaton cannot have final states, as infinite words never terminate. Rather, acceptance of the word is decided by looking at the infinite sequence of visited states during the run. • Probabilistic acceptance : An automaton need not strictly accept or reject an input. It may accept the input with some probability between zero and one. For example, quantum finite automaton, geometric automaton and metric automaton has probabilistic acceptance. Different combinations of the above variations produce many variety of automaton. Automata theory Automata theory is a subject matter which studies properties of various types of auto-mata. For example, following questions are studied about a given type of automata. • Which class of formal languages is recognizable by some type of auto-mata?(Recognizable languages) • Is certain automata closed under union, intersection, or complementation of for-mal languages?(Closure properties)

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Essential Discrete Mathematics for Computer Science

  • Harry Lewis, Rachel Zax(Authors)
  • 2019(Publication Date)
  • Princeton University Press

    (Publisher)

  The proof method used here is called pumping —it argues that any finite automaton accepting all the strings it is required to accept would also have to accept others it should not (strings with an extra j − i occurrences of a “pumped” in). While computer scientists are naturally most interested in how to devise clever solutions to solve diffi-cult problems, it has been one of the great achievements of the field (though rooted, as the √ 2 example shows, in ancient history) to develop ways of proving irrefutably that some problems simply can’t be solved using speci-fied methods. To make progress, either the methods have to change, or the problem has to be changed! Chapter Summary ■ A finite automaton or finite state machine is a simplified model of a computer. ■ A finite automaton is formally designated as a finite set of states, an alphabet of available symbols, a set of labeled arcs, a single start state (in a 19 • finite automata 197 diagram, marked by a > ), and a set of final states (each marked by a double circle). ■ A labeled arc represents a transition from one state to another in response to the specified input symbol. A λ -transition is a transition that consumes no input. ■ A finite automaton is deterministic (a “DFA”) if there is exactly one transition from each state in response to every symbol, and there are no λ -transitions: its behavior for any given input is fully determined. The function that maps a state and symbol to the corresponding next state is the DFA’s transition function . ■ A finite automaton is sometimes called a nondeterministic finite automaton (an “NDFA”) to emphasize that it is not necessarily deterministic. However, an NDFA may be deterministic—the DFAs are a proper subset of the NDFAs. ■ An NDFA can “guess” which of multiple paths to take; it accepts an input if there is any path from the start state to a final state that consumes the entire input.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Introduction to the Theory of Computation

  • Michael Sipser(Author)
  • 2012(Publication Date)
  • Cengage Learning EMEA

    (Publisher)

  This section gives a short overview of this important and beautiful subject. In defining DPDA s, we conform to the basic principle of determinism: at each step of its computation, the DPDA has at most one way to proceed according to its transition function. Defining DPDA s is more complicated than defining DFA s because DPDA s may read an input symbol without popping a stack symbol, and vice versa. Accordingly, we allow ε -moves in the DPDA ’s transition function even though ε -moves are prohibited in DFA s. These ε -moves take two forms: ε -input moves corresponding to δ ( q, ε ,x ) , and ε -stack moves corresponding to δ ( q,a, ε ) . A move may combine both forms, corresponding to δ ( q, ε , ε ) . If a DPDA can make an ε -move in a certain situation, it is prohibited from making a move in that same situation that involves processing a symbol instead of ε . Otherwise multiple valid computation branches might occur, leading to nondeterministic behavior. The formal definition follows. DEFINITION 2.39 A deterministic pushdown automaton is a 6-tuple ( Q, Σ , Γ ,δ,q 0 ,F ) , where Q , Σ , Γ , and F are all finite sets, and 1. Q is the set of states, 2. Σ is the input alphabet, 3. Γ is the stack alphabet, 4. δ : Q × Σ ε × Γ ε -→ ( Q × Γ ε ) ∪{∅} is the transition function, 5. q 0 ∈ Q is the start state, and 6. F ⊆ Q is the set of accept states. The transition function δ must satisfy the following condition. For every q ∈ Q , a ∈ Σ , and x ∈ Γ , exactly one of the values δ ( q,a,x ) ,δ ( q,a, ε ) ,δ ( q, ε ,x ) , and δ ( q, ε , ε ) is not ∅ . Copyright 2012 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience.

  Sign up to read

  Learn more about book