求这门语言的下推自动机 L={A^i B^j C^k | 2k <= i <= 3k OR j != (i+k) } 一叠
Find the pushdown automata of this language L={A^i B^j C^k | 2k <= i <= 3k OR j != (i+k) } with one stack
我找不到自动机，因为我只能用多个堆栈或集合论的交集来想象它。
语言：L = { A^i B^j C^k | 2k <= i <= 3k OR j != (i+k) }
此语言是 L' 和 L'' 两种语言的结合：
L' = { A^i B^j C^k | 2k <= i <= 3k }
L'' = { A^i B^j C^k | j != (i+k) }
如果我们计算出这些语言中每一种的 NPDA，我们可以通过以下方式为这两种语言的联合写下一个新的 NPDA：
- 引入新的开始状态，
q*
- 添加转换
f(q*,e,Z) = (q0',Z) 和 f(q*,e,Z) = (q0'',Z) 其中 e 是 epsilon/lambda，Z 是堆栈符号的底部，q0' 和 q0'' 分别是 L' 和 L'' 的 NPDA 的起始状态。
我们已经将较难的问题分解为两个较简单的问题，并想出了如何将较简单问题的答案放在一起来回答较难的问题。当涉及到计算机科学、数学以及很大程度上是计算机编程等正规科学时，这是您可以培养的最重要的技能。
L' 的 NPDA 应该是什么样的？它可以读取任意数量的 Bs，只要它们介于 As 和 Cs 之间。我们需要跟踪我们看到了多少个 A，比如说每次我们看到一个 A 就压入堆栈；一旦我们开始看到 Cs，我们就需要从堆栈中弹出 As。假设我们要空栈接受，我们需要移除所有的A；但是我们怎么知道要删除多少？如果我们有 2k = i，我们会为每看到一个 C 删除两个 A。如果我们有 i = 3k，我们会为每看到一个 C 删除三个 A。事实上，我们介于两者之间。这是概念上的困难。 不确定性 的概念——NPDA 中的 N——在这里至关重要。我们不需要确切地知道字符串将如何被接受；我们只需要一个 can 接受该语言的字符串，并且 can't 接受非该语言的字符串的过程。我们可以猜测是否需要在任何特定时刻从堆栈中删除两个或三个 A；这将保证我们不会超过 2k 和 3k 界限，并且它还允许我们得到介于两者之间的任何结果。为了使这项工作有效，我们可以简单地崩溃或拒绝所有失败的有效字符串执行，前提是其中一个可能的执行通过。
这是一个基于此描述的 NPDA，假设接受空栈和接受状态：
Q s S Q' S'
------------------------
// read A's and push onto stack
q0 A Z q0 AZ
q0 A A q0 AA
// begin reading B's
q0 B Z q1 Z
q0 B A q1 Z
// begin reading C's if no B's
q0 C A q2 -
q0 C A q3 -
// read B's
q1 B Z q1 Z
q1 B A q1 A
// begin reading C's if B's
q1 C A q2 -
q1 C A q3 -
// pop the final A for the last C read
q2 - A q4 -
// if popping three A's, pop the middle A
q3 - A q2 -
// pop the first A for each C read after the first C
q4 C A q2 -
q4 C A q3 -
// transition to separate accepting state if stack empty
q4 - Z qA -
在上述 NPDA 中，未显示会导致 "dead" 状态的转换。如果要显示它，请添加那些转换并调用状态 qR。在没有这些显式转换的情况下，NPDA 通常被理解为 "crash" 并拒绝输入。对于 L' 中的任何字符串，都会有一种方法通过此 NPDA 以状态 qA 结束，堆栈为空。
对于其他语言，我们可以进一步分解。 L'' 是两种语言 R' 和 R'':
的结合
R' = { A^i B^j C^k | j < i + k }
R'' = { A^i B^j C^k | j > i + k }
使用上面概述的相同构造，我们可以通过找到 R' 和 R'' 的 NPDA 并将这些答案放在一起来创建 L'' 的 NPDA。
对于R'，我们可以在读取A的时候将A压入栈中；我们可以弹出 As，如果有的话，或者在读取 Bs 时压入 Bs；最后，当读取 Cs 时，我们可以弹出 Bs，如果有的话，或者压入 Cs。当且仅当我们完成后堆栈顶部有 A 或 C 时，我们才会有 j < i + k。然后，我们可以进入接受状态，从栈中弹出 As 和 Cs 得到一个空栈。
对于R''，我们可以做同样的事情，在栈顶寻找一个B。我们可以进入接受状态并弹出 Bs 以清除堆栈。
R' R''
Q s S Q' S' Q s S Q' S'
----------------------- -----------------------
// count A's, first B/C // count A's, first B/C
q0' A Z q0' AZ q0'' A Z q0'' AZ
q0' A A q0' AA q0'' A A q0'' AA
q0' B Z q1' BZ q0'' B Z q1'' BZ
q0' B A q1' - q0'' B A q1'' -
q1' C Z q2' CZ q0'' C A q2'' CZ
q1' C A q2' CA q0'' C Z q2'' CA
// count B's, first C // count B's, first C
q1' B Z q1' BZ q1'' B Z q1'' BZ
q1' B A q1' - q1'' B A q1'' -
q1' B B q1' BB q1'' B B q1'' BB
q1' C Z q2' CZ q1'' C Z q2'' CZ
q1' C A q2' CA q1'' C A q2'' CA
q1' C B q2' CB q1'' C B q2'' CB
// count C's // count C's
q2' C Z q2' CZ q2'' C Z q2'' CZ
q2' C A q2' CA q2'' C A q2'' CA
q2' C B q2' - q2'' C B q2'' -
q2' C C q2' CC q2'' C C q2'' CC
// accept if A's or C's // accept if B's
q2' - A qA' - q2'' - B qA'- -
q2' - C qA' -
// accept if A's or C's // accept if B's
qA' - A qA' - qA'' - B qA'' -
qA' - C qA' -
因此，您的原始语言的 NPDA 如下：
Q s S Q' S'
-----------------------
q* - Z q0 Z
q* - Z q0' Z
q* - Z q0'' Z
将之前给出的所有其他转换添加到此，并将接受定义为在三种接受状态 qA、qA' 或 qA''.[=75 中的任何一种中由空堆栈进行接受=]
我找不到自动机，因为我只能用多个堆栈或集合论的交集来想象它。
语言：L = { A^i B^j C^k | 2k <= i <= 3k OR j != (i+k) }
此语言是 L' 和 L'' 两种语言的结合：
L' = { A^i B^j C^k | 2k <= i <= 3k }
L'' = { A^i B^j C^k | j != (i+k) }
如果我们计算出这些语言中每一种的 NPDA，我们可以通过以下方式为这两种语言的联合写下一个新的 NPDA：
- 引入新的开始状态，
q* - 添加转换
f(q*,e,Z) = (q0',Z)和f(q*,e,Z) = (q0'',Z)其中e是 epsilon/lambda，Z是堆栈符号的底部，q0'和q0''分别是L'和L''的 NPDA 的起始状态。
我们已经将较难的问题分解为两个较简单的问题，并想出了如何将较简单问题的答案放在一起来回答较难的问题。当涉及到计算机科学、数学以及很大程度上是计算机编程等正规科学时，这是您可以培养的最重要的技能。
L' 的 NPDA 应该是什么样的？它可以读取任意数量的 Bs，只要它们介于 As 和 Cs 之间。我们需要跟踪我们看到了多少个 A，比如说每次我们看到一个 A 就压入堆栈；一旦我们开始看到 Cs，我们就需要从堆栈中弹出 As。假设我们要空栈接受，我们需要移除所有的A；但是我们怎么知道要删除多少？如果我们有 2k = i，我们会为每看到一个 C 删除两个 A。如果我们有 i = 3k，我们会为每看到一个 C 删除三个 A。事实上，我们介于两者之间。这是概念上的困难。 不确定性 的概念——NPDA 中的 N——在这里至关重要。我们不需要确切地知道字符串将如何被接受；我们只需要一个 can 接受该语言的字符串，并且 can't 接受非该语言的字符串的过程。我们可以猜测是否需要在任何特定时刻从堆栈中删除两个或三个 A；这将保证我们不会超过 2k 和 3k 界限，并且它还允许我们得到介于两者之间的任何结果。为了使这项工作有效，我们可以简单地崩溃或拒绝所有失败的有效字符串执行，前提是其中一个可能的执行通过。
这是一个基于此描述的 NPDA，假设接受空栈和接受状态：
Q s S Q' S'
------------------------
// read A's and push onto stack
q0 A Z q0 AZ
q0 A A q0 AA
// begin reading B's
q0 B Z q1 Z
q0 B A q1 Z
// begin reading C's if no B's
q0 C A q2 -
q0 C A q3 -
// read B's
q1 B Z q1 Z
q1 B A q1 A
// begin reading C's if B's
q1 C A q2 -
q1 C A q3 -
// pop the final A for the last C read
q2 - A q4 -
// if popping three A's, pop the middle A
q3 - A q2 -
// pop the first A for each C read after the first C
q4 C A q2 -
q4 C A q3 -
// transition to separate accepting state if stack empty
q4 - Z qA -
在上述 NPDA 中，未显示会导致 "dead" 状态的转换。如果要显示它，请添加那些转换并调用状态 qR。在没有这些显式转换的情况下，NPDA 通常被理解为 "crash" 并拒绝输入。对于 L' 中的任何字符串，都会有一种方法通过此 NPDA 以状态 qA 结束，堆栈为空。
对于其他语言，我们可以进一步分解。 L'' 是两种语言 R' 和 R'':
R' = { A^i B^j C^k | j < i + k }
R'' = { A^i B^j C^k | j > i + k }
使用上面概述的相同构造，我们可以通过找到 R' 和 R'' 的 NPDA 并将这些答案放在一起来创建 L'' 的 NPDA。
对于R'，我们可以在读取A的时候将A压入栈中；我们可以弹出 As，如果有的话，或者在读取 Bs 时压入 Bs；最后，当读取 Cs 时，我们可以弹出 Bs，如果有的话，或者压入 Cs。当且仅当我们完成后堆栈顶部有 A 或 C 时，我们才会有 j < i + k。然后，我们可以进入接受状态，从栈中弹出 As 和 Cs 得到一个空栈。
对于R''，我们可以做同样的事情，在栈顶寻找一个B。我们可以进入接受状态并弹出 Bs 以清除堆栈。
R' R''
Q s S Q' S' Q s S Q' S'
----------------------- -----------------------
// count A's, first B/C // count A's, first B/C
q0' A Z q0' AZ q0'' A Z q0'' AZ
q0' A A q0' AA q0'' A A q0'' AA
q0' B Z q1' BZ q0'' B Z q1'' BZ
q0' B A q1' - q0'' B A q1'' -
q1' C Z q2' CZ q0'' C A q2'' CZ
q1' C A q2' CA q0'' C Z q2'' CA
// count B's, first C // count B's, first C
q1' B Z q1' BZ q1'' B Z q1'' BZ
q1' B A q1' - q1'' B A q1'' -
q1' B B q1' BB q1'' B B q1'' BB
q1' C Z q2' CZ q1'' C Z q2'' CZ
q1' C A q2' CA q1'' C A q2'' CA
q1' C B q2' CB q1'' C B q2'' CB
// count C's // count C's
q2' C Z q2' CZ q2'' C Z q2'' CZ
q2' C A q2' CA q2'' C A q2'' CA
q2' C B q2' - q2'' C B q2'' -
q2' C C q2' CC q2'' C C q2'' CC
// accept if A's or C's // accept if B's
q2' - A qA' - q2'' - B qA'- -
q2' - C qA' -
// accept if A's or C's // accept if B's
qA' - A qA' - qA'' - B qA'' -
qA' - C qA' -
因此，您的原始语言的 NPDA 如下：
Q s S Q' S'
-----------------------
q* - Z q0 Z
q* - Z q0' Z
q* - Z q0'' Z
将之前给出的所有其他转换添加到此，并将接受定义为在三种接受状态 qA、qA' 或 qA''.[=75 中的任何一种中由空堆栈进行接受=]