难以理解w1=w|w|的含义

Question

好的，我有一个语言L={w:|w|≥1，和w1=w|w|}。

w1=w|w|是w下标1和w下标|w|。

我搞不懂w1=w|w|是什么意思。| w |表示w的长度，但是如果我们像第一个单词那样将w1设置为语言中的第|w|个单词，那么它到底是什么？当我们在这里说|w|时，我们谈论的是哪个单词的长度？

Answer 1

好的，我有一个语言L={w:|w|≥1，和w1=w|w|}。w1=w|w|是w下标1和w下标|w|。

给定1和|w|是下标，这意味着L是长度至少为一个(|w|≥1)的单词w的语言，其第一个和最后一个符号相同。根据你的描述，似乎没有其他解释比这更有可能了。

这样的语言对于任何字母A都是正则的。假设A= {a1，a2，...，an}是任意字母表(所以n≥1)。您的语言的正则表达式由(a1)((A*)(a1))* + (a2)((A*)(a2))* + ... + (an)((A*)(an))*给出。DFA会有这样的转换表：

q    s    q'
---  ---  ---

q0   a1   q1    // remember the first symbol
q0   a2   q2    // by moving to a unique state
...  ...  ...   // per symbol
q0   an   qn

q1   a1   q1    // q1 is accepting and q1' is not
q1   A\a1 q1'   // move between these and only
q1'  a1   q1    // accept if the last thing seen
q1'  A\a1 q1'   // is a1

q2   a2   q2    // q2 is accepting and q2' is not
q2   A\a2 q2'   // move between these and only
q2'  a2   q2    // accept if the last thing seen
q2   A\a2 q2'   // is a2

...

qn   an   qn    // qn is accepting and qn' is not
qn   A\an qn'   // move between these and only
qn'  an   qn    // accept if the last thing seen
qn'  A\an qn'   // is an

该DFA有2n +1个状态。我们可以使用Myhill-Nerode来证明它是最小的，因为我们证明了这些状态中的每一个都代表一个不同的等价类，并且不存在其他不同的等价类(在不可区分关系下)。

1. 空字符串是可区分的，并且与状态q0相对应。
2. 所有长度一字符串都是可区分的，并且与状态q1到qn相对应。
3. 所有长度-由两个不同符号组成的两个字符串是可区分的，并且与状态q1‘到qn’相对应。以相同符号开头和结尾的长度为2或更长的
4. 字符串与与状态q1到qn相对应的长度一字符串是不可区分的。

H112长度为3或更长且以不同符号开头和结尾的字符串与与状态代码‘到qn’相对应的长度2字符串是不可区分的。