自动机理论:上下文无关语法到DFA的转换

Question

如何将上下文无关语法转换为DFA?这很容易，如果我们有这样的过渡A-> A B，但是当我们有转换为A-> A B c，那么我们应该如何表示它为DFA

Answer 1

没有将任意CFG转换为DFA的通用过程。例如，考虑以下CFG:

S→aSb | ε

此语法适用于语言{aⁿbⁿ | n≥0}，它是一种规范的非正则语言。由于我们只能为常规语言构建DFA，因此无法使用与此CFG

Answer 2

首先，您应该将您的语言转换为CNF(乔姆斯基范式)。然后转换步骤如下:

1. 将其转换为左/右语法称为正则语法

2. 将正则语法转换为有限自动机自动机的过渡得到如下对于每个产品A -> aB，使δ(A, A) = B，即使A从A到B标记为' A '。对于每个产品A -> A，使δ(A, A) =最终状态。对于每个产品A -> λ，令δ(A， λ) = A, A为最终状态。

Answer 3

• 。对于这些语法，不能形成DFA。
• 为什么?
• 因为它需要内存。a.
的发生记忆
• 是的。它是CFL(无上下文语言)。
• 我们可以设计一个PDA (Push down automata)。这里，内存(STACK)是使用)。为推动, b