我找不到自动机，因为我只能用多个堆栈或集合论的交集来想象它。
问问题
327 次
1 回答
1
语言：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)其中eepsilon/lambdaZ是堆栈符号的底部，q0'和分别是和q0''的 NPDA 的起始状态。L'L''
我们将较难的问题分解为两个较简单的问题，并想出如何将较容易的问题的答案放在一起以回答较难的问题。当涉及到计算机科学、数学以及在很大程度上是计算机编程等形式科学时，这是您可以培养的最重要的技能。
NPDA 应该是什么L'样的？它可以读取任意数量的Bs，只要它们位于As 和Cs 之间。我们需要跟踪A我们看到了多少个 s，比如A每次看到一个就将一个压入堆栈；A一旦我们开始看到s ，我们就需要将 s 从堆栈中弹出C。假设我们想通过空栈接受，我们需要删除所有的As；但是我们怎么知道要删除多少？如果我们有，我们会为每看到一个 s2k = i删除两个s。如果我们有，我们会为每看到一个 s删除三个s。事实上，我们介于两者之间。这是概念上的困难。非决定论的概念ACi = 3kAC- NPDA 中的 N - 在这里至关重要。我们不需要确切知道字符串是如何被接受的；我们只需要一个可以接受该语言中的字符串并且不能接受非该语言中的字符串的进程。我们可以猜测是否需要A在任何特定时刻从堆栈中删除两个或三个 s；这将保证我们不会超出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 中，没有显示会导致“死”状态的转换。如果要显示它，请添加这些转换并调用 state qR。在没有这些显式转换的情况下，NPDA 通常被理解为“崩溃”并拒绝输入。对于 中的任何字符串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 }
使用上面概述的相同结构，我们可以L''通过找到 NPDAR'并将R''这些答案放在一起来创建 NPDA。
对于R'，我们可以A在读取 s 时将 s 压入栈中A；在读取 s 时，我们可以弹出As，如果有的话，或者推送s；最后，我们可以在读取 s 时弹出s，如果有的话，或者推送s。当且仅当我们完成时堆栈顶部有一个or时，我们才会有。然后，我们可以移动到接受状态并从堆栈中弹出s 和s 以获得一个空堆栈。BBBCCj < i + kACAC
对于R''，我们可以做同样的事情并B在堆栈顶部查找 a 。我们可以移动到接受状态并 popB清除堆栈。
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''。
于 2017-11-14T16:54:12.867 回答