# pushdown automata

Published articles for pushdown automata.

This is one page of public article previews, not the complete archive. Follow Next page to continue. Summaries are not the original full articles.

## Turing Machines--A Primer

DevFeed: [Turing Machines--A Primer](<https://devfeed.tech/articles/turing-machines-a-primer-40218.md>)

Original publisher: [Read original article](<https://www.jeremykun.com/2011/07/04/turing-machines-a-primer/>)

Published: 2011-07-04T16:35:44Z

Content type: tutorial

Language: en

Sources: [Jeremy Kun](<https://devfeed.tech/sources/jeremy-kun.md>)

Topics: [Automaton](<https://devfeed.tech/topics/automaton.md>), [function](<https://devfeed.tech/topics/function.md>)

Tags: [acceptance](<https://devfeed.tech/tags/acceptance.md>), [computability-theory](<https://devfeed.tech/tags/computability-theory.md>), [computers](<https://devfeed.tech/tags/computers.md>), [concepts](<https://devfeed.tech/tags/concepts.md>), [decidability](<https://devfeed.tech/tags/decidability.md>), [halting-problem](<https://devfeed.tech/tags/halting-problem.md>), [input](<https://devfeed.tech/tags/input.md>), [machine](<https://devfeed.tech/tags/machine.md>), [mathematics](<https://devfeed.tech/tags/mathematics.md>), [primer](<https://devfeed.tech/tags/primer.md>), [process](<https://devfeed.tech/tags/process.md>), [pushdown-automata](<https://devfeed.tech/tags/pushdown-automata.md>), [state](<https://devfeed.tech/tags/state.md>), [symbols](<https://devfeed.tech/tags/symbols.md>), [turing-machines](<https://devfeed.tech/tags/turing-machines.md>)

### AI overview

This tutorial introduces Turing machines as a model of computation. It defines their states, tape symbols, input symbols, initial state, accepting and rejecting states, and transition function, then explains how the tape, read-write head, state transitions, and halting behavior work.

### Source excerpt

We assume the reader is familiar with the concepts of determinism and finite automata, or has read the corresponding primer on this blog. The Mother of All Computers Last time we saw some models for computation, and saw in turn how limited they were. Now, we open Pandrora's hard drive: Definition: A Turing machine is a tuple $ (S, \Gamma, \Sigma, s_0, F, \tau)$, where $ S$ is a set of states, $ \Gamma$ is a set of tape symbols, including a special blank symbol $ b$, $ \Sigma \subset \Gamma$ is a set of input symbols, not including $ b$, $ s_0$ is the initial state, $ A \subset S$ is a set of accepting states, $ R \subset S$ is a set of rejecting states, $ \tau: S - (A \cup R) \times \Gamma \to S \times \Gamma \times \left \{ L, R \right \}$ is a partial function called the transition function, where $ L, R$ correspond to "left shift" and "right shift," respectively.

## Determinism and Finite Automata--A Primer

DevFeed: [Determinism and Finite Automata--A Primer](<https://devfeed.tech/articles/determinism-and-finite-automata-a-primer-40217.md>)

Original publisher: [Read original article](<https://www.jeremykun.com/2011/07/02/determinism-and-finite-automata-a-primer/>)

Published: 2011-07-02T23:41:30Z

Content type: tutorial

Language: en

Sources: [Jeremy Kun](<https://devfeed.tech/sources/jeremy-kun.md>)

Topics: [Automaton](<https://devfeed.tech/topics/automaton.md>), [function](<https://devfeed.tech/topics/function.md>)

Tags: [computability-theory](<https://devfeed.tech/tags/computability-theory.md>), [computing](<https://devfeed.tech/tags/computing.md>), [context-free-languages](<https://devfeed.tech/tags/context-free-languages.md>), [deterministic-finite-automata](<https://devfeed.tech/tags/deterministic-finite-automata.md>), [finite-state-machines](<https://devfeed.tech/tags/finite-state-machines.md>), [function](<https://devfeed.tech/tags/function.md>), [input](<https://devfeed.tech/tags/input.md>), [language](<https://devfeed.tech/tags/language.md>), [mathematics](<https://devfeed.tech/tags/mathematics.md>), [nondeterministic-finite-automata](<https://devfeed.tech/tags/nondeterministic-finite-automata.md>), [primer](<https://devfeed.tech/tags/primer.md>), [pushdown-automata](<https://devfeed.tech/tags/pushdown-automata.md>), [regular-languages](<https://devfeed.tech/tags/regular-languages.md>), [string](<https://devfeed.tech/tags/string.md>), [turing-machines](<https://devfeed.tech/tags/turing-machines.md>)

### AI overview

This primer introduces computation as a function that maps input to output, then develops a more rigorous model based on finite alphabets and strings. It explains how a computational model recognizes a language by accepting or rejecting strings.

### Source excerpt

The first step in studying the sorts of possible computations (and more interestingly, those things which cannot be computed) is to define exactly what we mean by a "computation." At a high level, this is easy: a computation is simply a function. Given some input, produce the appropriate output. Unfortunately this is much too general. For instance, we could define almost anything we want in terms of functions. Let $ f$ be the function which accepts as input the date of California Super Lotto drawings, and returns the set of winning numbers for that date.