regular-language - 设计接受特定长度字符串的 NFA

Question

我期待设计一个接受某种字符串的 FA，它接受一些 A 和 B。

首先是一个字符串，其中 A 的数量是 B 的五倍。

我的意思是 L={w∈{A,B}* and (nA(W)-nB(W) mod 5=0)

还有一个 FA，它接受字符串中不同数量的字符：

L={A^n B^m C^k | n,k>0 and m>3}

我设计了一些 FA 但它们在这个复杂的字符串上不能完美地工作。

我应该如何设计这个有什么帮助吗？

Answer 1

不幸的是，您的问题令人困惑，因为英文文本与数学公式不符。我将尝试回答这四个问题：

• 一种由 {a,b} 上的字符串组成的语言，其中 a (= #a(w)) 的数量是 b (#b(w)) 的数量的五倍， L = { w in {a,b}* : #a(w)>#b(w) and #a(w)=#b(w)mod5 }

  NFA 无法做到这一点。证明很简单，使用带有字符串 a^pb^5p 的泵引理 (PL)，其中 p 是 PL 的常数

• 对于您编写的语言：L={w∈{A,B}* : (nA(W)-nB(W)) mod 5=0}您可以使用由 5 个状态循环组成的 DFA 来完成。

  转换是，如果你读 a 顺时针方向，如果你读 b 逆时针方向。随机选择一个状态作为初始状态，相同的状态将作为最终状态。

• 对于语言 L={A^n B^m C^k | n,k>0 和 m>3}，如果您将 L 读为L=A(A)* B(B)* c^4(C)*

• 对于接受字符串中不同数量的字符的语言（比如说a，b）。语言应该是R={ w in {a,b}* : #a(w) not equal #b(w)}

  这种语言再次无法被 NFA 识别。如果这种语言是常规的（被 NFA 识别），那么这种语言也是：

  L=a*b* intersection (R complement). 语言 L 是{a^n b^n/ n non-negative integer}.

  语言 L 是大多数书籍中谈论非常规语言时的第一个示例。

希望这个答案对您有所帮助。