19th Ave New York, NY 95822, USA

# 数学代考| Pushdown Automata 离散数学代写

## 数学代写| Pushdown Automata 离散代考

my-assignmentexpert愿做同学们坚强的后盾，助同学们顺利完成学业，同学们如果在学业上遇到任何问题，请联系my-assignmentexpert™，我们随时为您服务！

## 离散数学代写

7.3 Pushdown Automata
A pushdown automaton (PDA) is essentially a finite-state machine with a stack, and it includes three components namely an input tape; a control unit and a potentially infinite stack. The stack head scans the top symbol of the stack, and two operations (push or pop) may be performed on the stack. The push operation adds a new symbol to the top of the stack, whereas the pop operation reads and removes an element from the top of the stack (Fig. 7.4). element from the top of the stack (Fig. 7.4).
A push down automaton may remember a potentially infinite amount of information, whereas a finite-state automaton remembers only a finite amount of information. A PDA also differs from a FSM in that it may use the top of the stack performance of a transition. The input and current state determine the transition in a finite-state machine, and a FSM has no stack to work with.

A pushdown automaton is defined formally as a 7-tuple $\left(\Sigma, \mathrm{Q}, \Gamma, \delta, q_{0}, \mathrm{Z}, F\right)$. The set $\Sigma$ is a finite set which is called the input alphabet; the set $Q$ is a finite set of states; $\Gamma$ is the set of stack symbols; $\delta$ is the transition function which maps $Q \times{\Sigma \cup{\varepsilon}}^{3} \times \Gamma$ into finite subsets of $Q \times \Gamma^{* 2} ; q_{0}$ is the initial state; $Z$ is the initial stack top symbol on the stack (i.e. $Z \in \Gamma$ ) and $F$ is the set of accepting states (i.e. $F \subseteq Q$ ).

Figure $7.5$ shows a transition from state $q_{1}$ to $q_{2}$, which is labelled as $a$, $b \rightarrow c$. This means that at if the input symbol $a$ occurs in state $q_{1}$, and the symbol on the top of the stack is $b$, then $b$ is popped from the stack and $c$ is pushed onto the stack. The new state is $q_{2}$.

In general, a pushdown automaton has several transitions for a given input symbol, and so pushdown automata are mainly non-deterministic. If a pushdown automaton has at most one transition for the same combination of state, input
${ }^{3}$ The use of ${\Sigma \cup{\varepsilon}}$ is to formalize that the PDA can either read a letter from the input, or proceed leaving the input untouched.
126
7 Automata Theory
Fig. $7.5$
symbol and top of stack symbol it is said to be a deterministic PDA (DPDA). The set of strings (or language) accepted by a pushdown automaton $M$ is denoted $L(M)$. The class of languages accepted by pushdown automata is the context free languages, and every context free grammar can be transformed into an equivalent non-deterministic pushdown automaton. Chapter 12 has more detailed information on the classification of languages.
Example (Pushdown Automata)
Construct a non-deterministic pushdown automaton which recognizes the language $\left{0^{n} 1^{n} \mid n \geq 0\right} .$
Solution
We construct a pushdown automaton $M=\left(\Sigma, Q, \Gamma, \delta, q_{0}, Z, F\right)$ where $\Sigma=$ ${0,1} ; Q=\left{q_{0}, q_{1}, q_{f}\right} ; \Gamma={A, Z} ; q_{0}$ is the start state; the start stack symbol is $Z$ and the set of accepting states is given by $\left{q_{f}\right}:$ The transition function (relation) $\delta$ is defined by

1. $\left(q_{0}, 0, Z\right) \rightarrow\left(q_{0}, A Z\right)$
2. $\left(q_{0}, 0, A\right) \rightarrow\left(q_{0}, A A\right)$
3. $\left(q_{0}, \varepsilon, Z\right) \rightarrow\left(q_{1}, Z\right)$
4. $\left(q_{0}, \varepsilon, A\right) \rightarrow\left(q_{1}, A\right)$
5. $\left(q_{1}, 1, A\right) \rightarrow\left(q_{1}, \varepsilon\right)$ 6. $\left(q_{1}, \varepsilon, Z\right) \rightarrow\left(q_{f}, Z\right)$
The transition function (Fig. 7.6) essentially says that whenever the value 0 occurs in state $q_{0}$ then $\mathrm{A}$ is pushed onto the stack. Parts (3) and (4) of the transition function essentially state that the automaton may move from state $q_{0}$ to state $q_{1}$ at any moment. Part (5) states when the input symbol is 1 in state $q_{1}$ then one symbol state $q_{1}$ to the accepting state $q_{f}$ only when the stack consists of the single stack symbol Z.

7.3 下推自动机

${ }^{3}$ ${\Sigma \cup{\varepsilon}}$ 的使用是为了表明 PDA 可以从输入中读取字母，或者继续保持输入不变。
126
7 自动机理论

1. $\left(q_{0}, 0, Z\right) \rightarrow\left(q_{0}, A Z\right)$
2. $\left(q_{0}, 0, A\right) \rightarrow\left(q_{0}, A A\right)$
3. $\left(q_{0}, \varepsilon, Z\right) \rightarrow\left(q_{1}, Z\right)$
4. $\left(q_{0}, \varepsilon, A\right) \rightarrow\left(q_{1}, A\right)$
5. $\left(q_{1}, 1, A\right) \rightarrow\left(q_{1}, \varepsilon\right)$ 6. $\left(q_{1}, \varepsilon, Z\right ) \rightarrow\left(q_{f}, Z\right)$
转换函数（图 7.6）本质上说，每当状态 $q_{0}$ 出现值 0 时，$\mathrm{A}$ 就会被压入堆栈。转移函数的 (3) 和 (4) 部分实质上表明自动机可以随时从状态 $q_{0}$ 移动到状态 $q_{1}$。第 (5) 部分说明当输入符号在状态 $q_{1}$ 中为 1 时，一个符号状态 $q_{1}$ 到接受状态 $q_{f}$ 仅当堆栈由单个堆栈符号 Z 组成时.

## 图论代考

(a) 假设一个操作有 $m$ 个可能的结果，而第二个操作有 $n$ 个可能的结果，那么执行第一个操作后执行第二个操作时可能结果的总数是 $m \times n$ (Product Rule )。
(b) 假设一个操作有 $m$ 个可能的结果，而第二个操作有 $n$ 个可能的结果，那么第一个操作或第二个操作的可能结果总数由 $m+n$ 给出（求和规则） .

$(1, \mathrm{H}),(2, \mathrm{H}),(3, \mathrm{H}),(4, \mathrm{H}),(5, \mathrm{H}) ,(6, \mathrm{H}),(1, \mathrm{~T}),(2, \mathrm{~T}),(3, \mathrm{~T}),(4, \mathrm{ ~T}),(5, \mathrm{~T}),(6, \mathrm{~T})$

5.7 排列组合
97

(a) 假设有一组 367 人，那么必须至少有两个人的生日相同。

(b) 假设有 102 名学生参加了一次考试（考试的结果是 0 到 100 之间的分数）。然后，至少有两名学生获得相同的分数。

## 密码学代考

• Cryptosystem
• A system that describes how to encrypt or decrypt messages
• Plaintext
• Message in its original form
• Ciphertext
• Message in its encrypted form
• Cryptographer
• Invents encryption algorithms
• Cryptanalyst
• Breaks encryption algorithms or implementations

## 编码理论代写

1. 数据压缩（或信源编码
2. 前向错误更正（或信道编码
3. 加密编码
4. 线路码