常规语言作为定期集合的有限联盟

Question

是真的，每个常规语言都可以表示为周期性集的有限联合？换句话说，如果 $ l $ 是常规的，那么就存在有限集 $ a_1，\ dots，a_n，b_1，\ dots，b_n $ 这样

$$ l= a_1 \ cdot b_1 ^ * \ cap \ cdots \ cup a_n \ cdot b_n ^ *。$$

我知道这是针对一元字母表的常规语言是真的，但我不确定一般字母表。

Answer 1

此表单的每种语言都可以表示为没有嵌套的Kleene Star的正则表达式。也就是说，它的 star height 是 $ 1 $ 。 star height shierarchy 是严格的，特别是，众所周知，语言 $（a ^ * b ^ * c）^ * $ 不能以该表格表示。二进制字母表中的示例是 $（aa（ab）^ * bb（ab）^ *）^ * $ 。

Answer 2

@yuvalfilmus的答案非常好，并指出您进入星高度的导入概念。但让我添加一点。我们将显示您的表单的语言给出了Star Height One的语言的适当子集。但首先，一些沉思可能接近你的表格。

一般常规语言

首先，可能是常规 $ l \ subseteq \ sigma ^ * $ ，由完整的确定性自动机 $ a=（\ sigma，q，\ delta，q_0，f）$ 。 对于 $ q \ in q $ 和 $ e \ subseteq q $ ，写 $ l_ {q，e}（a）$ 的语言 由 $（\ sigma，q，\ delta，q，e）$ ，即，将start状态更改为 $ Q $ 以及 $ e $ 的那样。 然后，我们可以写 $$ l=bigcup_ {q \在f} l_ {q_0，q}（a）l_ {q，\ \ {q \}}（a）^ * $$ 这个结果似乎是民间传说，并且很容易跟随。通过更换，它可能有点加强 $ l_ {q_0，\ {q \}}（a）按语言的$ $$ \ {u \ in l_ {q_0，\ {q \}} \ mid \ delta（q_0，v）\ ne q \ mbox {为每个正确的前缀$ v $ v $ u $ u $} \} $$ 在上面的等式中。它具有在它中没有单词的属性是另一个单词的适当前缀。这种分解的变体以及更多的细化，出现在书籍自动机，语言和机器，卷a 的名称下，在迭代的上分解下。< / p>

换向和有界常规语言

其他形式，更贴近您的，并且可以获得您提到的若干语言案例的正确概括，可以获得有界和换向的常规语言。一种语言是换向，如果它在字母排列下关闭。例如， $ \ {ab，ba \} $ 是换向，而 $ \ {ab \} $ 不是。语言 $ l \ subseteq \ sigma ^ * $ 是界限，if $ l \ subseteq w_1 ^ * \ cdots w_n ^ * $ 对于 $ w_i \ in \ sigma ^ * $ 。在下文中，让我们通过 $ \ indond $ shuffle 两种语言，而且，对于 $ l \ subseteq \ sigma ^ * $ ，by $ l ^ {\ indond，*}=bigcup_ {n \ ge 0} \ undbrace {l \ diamond \ ldots \ diamond l} _ {\ mbox {$ n $ times} $ 迭代洗牌。此外，by $ \ operatorname {perm}：2 ^ {\ sigma ^ *} \ to 2 ^ {\ sigma *} $ 表示允许关闭< / em>，或换向关闭，即添加偏转的所有单词。 例如， $ \ operatorname {perm}（\ {ab \}）={ab，ba \} $ 。

注意， $ l \ subseteq w ^ * $ 是常规iff $ l= w ^ n（w ^ p ）^ * $ 一些 $ n，p \ ge 0 $ 。通过注意到 $ \ {n：w ^ n \ in l \} $ 最终是周期性的（可以被视为常规联合语言）。< / p>

是吉斯堡/斯文我们有

语言 $ l \ subseteq w_1 ^ * \ cdots w_r ^ * $ 是常规iff它是 $ l_1 \ cdots l_r $ ，其中每个 $ l_i \ subseteq w_i ^ * $ 是常规的。

此外，如果 $ \ sigma={a_1，\ ldots，a_k \} $ 和 $ l \ subseteq \ sigma ^ * $ 是换向和常规的，它是可能显示 $$ l=bigcup_ {i= 1} ^ n \ operatorname {perm}（u_i）\ diamond \ operatorname {perm}（n_i）^ {\ diamond，*} $$ 对于有限套装 $ n_i \ subseteq a_1 ^ * \ cup \ ldots \ cup a_k ^ * $ with $ | n_i \ cap A_J ^ * | \ Le 1 $ 。

还，如同说明 和<一个href=“https://arxiv.org/abs/2005.04042”rel=“nofollow noreferrer”>这里，常规语言 $ l $ 结束 $ \ sigma={a_1，\ ldots，a_k \} $ 是换向IFF $$ l=bigcup_ {i= 1} ^ n u_ {i，1} \

钻石\ ldots \钻石u_ {i，k} $$ 对于Unary常规语言 $ u_ {i，j} \ subseteq a_j ^ * $ 使用 $ i \ in \ {1，\ ldots，n \} $ 和 $ j \ in \ {1，\ ldots，k \} $ 。

所有这些结果都密切相关。请注意，对于一元语言，它们都将它们缩小到您所陈述的表格。

形式语言的必要条件

我将状态的条件涉及拓扑和无限单词。例如，它产生了 $ b ^ * a $ 和 $（b ^ * a）^ * $ 无法用您的表格写入。后者有星高度，注意，星形高度可以通过循环等级来表征，请参阅 eggan的定理。 但是，我确实想给出一个独立的，不同的争论，而不是基于星高度。让 $ \ sigma ^ {\ oomega} $ 是 $ \ sigma $ 上的无限单词集。定义运算符 $ w：2 ^ {\ sigma ^ *} \到2 ^ {\ sigma ^ {\ oomega}} $ by，for $ l \ subseteq \ sigma ^ * $ ， $$ w（l）={\ xi \ in \ sigma ^ {\ oomega} \ mid \ mbox {$ \ xi $在$ l $} \}中有无数的许多前缀。 $$ 然后 \ begin {align *} w（b ^ * a）＆=imptyset \\ w（（b ^ * a）^ *）＆={\ xi \ in \ sigma ^ {\ omega} \ mid \ mbox {$ \ xi $ of fly mony $ a $ s。 } \}。 \结束{align *} 遵守这一点 $$ W（U \ Cup V）= W（U）\ Cup v（v）， $$ AS，如果 $ \ xi \ In w（u \ cup v）$ ，那么，由仔猪原理，至少一个 $ U $ 或 $ v $ ，或两者，必须包含无数的 $ \ xi的前缀$ 。此外，在您的表单中，我们可以假设所有集合 $ a_i $ 是单例，因为连接分布在联盟上。

让我们检查表单 $ l= u（u_1 + \ ldots + u_n）^ * $ ，这是表单的一部分。 set $ \ gamma={b_1，\ ldots，b_n \} $ ，辅助字母表，并考虑同头形式 $ h：\ gamma \ to \ sigma ^ * $ 给出 $ h（b_i）= u_i $ ，即用相应的单词替换每个字母。这种同性恋也可以应用于 $ \ gamma ^ {\ oomega} $ 中的无限字。我们有 $$ w（u（u_1 + \ ldots + u_n）^ *）={uh（\ xi）\ mid \ xi \ In \ gamma ^ {\ omega} \}。 $$ 特别是，如果所有SET $ B_I $ 是单例， $ w（l）$ 是有限的，和 $ w（l）\ ne \ mimptyset $ 对于表单的每种无限语言。

通过最后一个观察， $ b ^ * a $ 无法用您的表单写入。所以，这是一个非常简单的例子，甚至是星高度。 但让我们展示 $ l=（b ^ * a）^ * $ 也不能以这种方式写入。假设它可以是，那么一组无限单词，所有这些都具有无限数的 $ a $ ，可以根据同性恋编写 $ h：\ gamma ^ * \ to \ sigma ^ * $ 如上所述，即， $$ \ {\ xi \ in \ sigma ^ {\ omega} \ mid \ mbox {$ \ xi $ flyly $ a $ s。 } \}= u h（\ gamma ^ {\ omega}） $$ 对于一些 $ u \ in \ sigma ^ * $ 。 让 $ m={| h（x）| ：x \ in \ gamma \} + | U | $ 。 然后 $ ub ^ maaaaa \ cdots $ 是以这种语言， 这意味着 $ h（x）\在b ^ + $ 中，对于某些 $ x \ In \ gamma $ 。 但是 $ ubbbbbbb \ cdots \ In uh（\ gamma ^ {\ omega}）$ ，它是一个矛盾，因为它只包含一个有限数量的 $ a $ 。因此， $（b ^ * a）^ * $ 无法以这种方式写入。 $ \ square $