regular-language - 这两种常规语言是一样的吗？

Question

给定一个字母{a, b}where表示 的出现次数，以及的出现次数：NaaNbb

1. L1 = {xy | Na(x) = Nb(y)}
2. L2 = {w | Na(w) and Nb(w) are even number}

具有四个状态并使用 mod 的单个 DFA 不能接受两种语言吗？

Answer 1

不，因为两种语言不同，所以您不能为两种语言绘制单个 DFA。

自动机唯一地定义了一种语言，但是对于一种语言，当然可以有多个自动机称为“等效自动机”。

语言 是一种常规语言。这种语言的正则表达式是：L1 = A = {xy | Na(x) = Nb(y)}

(a + b)*a(a + b)*b(a + b)*  +  ^

要理解这种语言和正则表达式，请阅读：“显示以下集合{a, b}是正则的”。

语言 也是一种常规语言。这种语言的正则表达式是：L2 = A = {w | Na(w) and Nb(w) are even number}

((a + b(aa)*ab)(bb)*(ba(aa)*ab(bb)*)*a + (b + a(bb)*ba)(aa)*(ab(bb)*ba(aa)*)*b)*

要理解这种语言和正则表达式，请阅读：“Need Regular Expression for Finite Automata”。

但是两种语言并不相等，因为语言 L1 中有一些不属于语言 L2ab的字符串，例如 L1 中的字符串但不包含偶数个a，b因此不属于语言 L2。

注意：语言 L2 不是语言 L1 的子集，因为在 L2 中，可能存在偶数长度和单个符号的字符串，如aa, aaaa, bb，bbbb但这些字符串不是 L1 的成员。

两种语言都不同，因此两种语言都不能使用单一的 DFA 。