如何将此描述翻译成一种语言？
How to translate this description into a language?
我正在尝试将以下描述“所有 0 和 1 的字符串，其中 0 的数量至少与 1 的数量一样多”翻译成一种语言。
我想过{L= 0^n1^n | n>0} 但“至少”部分呢？这是否意味着我可以拥有比 1 更多的 0？ （例如 000011）（或者 {L = 0^j1^k | j>k, j,k >0} ？）我不完全确定它是如何工作的，所以任何帮助将不胜感激:)
（顺便说一句，我这样做是为了证明泵送引理不规则，欢迎任何提示哈哈）
对此没有一个非常令人满意的集合生成器表示法。令#k(w) 为符号 k 在字符串 w 中出现的次数，其中 w 是包含符号 k 的某个字母表上的字符串。那么你的语言是 { w in {0, 1}* | #0(w) >= #1(w) }。我不确定这样写下来有多大帮助。
为了证明语言不是正则的，我建议对正则语言使用泵引理，或者直接从简单的描述中使用 Myhill-Nerode 定理。对于抽取引理，选择 1^p 0^p 并论证抽取增加了太多的 1。要使用 Myhill-Nerode，请选择序列 1、11、...、1^k、...，并论证可以附加到 1^k 以得到您的语言中的字符串的最短字符串是 0^k ，意味着所有 1^k 都是可区分的。
我正在尝试将以下描述“所有 0 和 1 的字符串，其中 0 的数量至少与 1 的数量一样多”翻译成一种语言。
我想过{L= 0^n1^n | n>0} 但“至少”部分呢？这是否意味着我可以拥有比 1 更多的 0？ （例如 000011）（或者 {L = 0^j1^k | j>k, j,k >0} ？）我不完全确定它是如何工作的，所以任何帮助将不胜感激:)
（顺便说一句，我这样做是为了证明泵送引理不规则，欢迎任何提示哈哈）
对此没有一个非常令人满意的集合生成器表示法。令#k(w) 为符号 k 在字符串 w 中出现的次数，其中 w 是包含符号 k 的某个字母表上的字符串。那么你的语言是 { w in {0, 1}* | #0(w) >= #1(w) }。我不确定这样写下来有多大帮助。
为了证明语言不是正则的，我建议对正则语言使用泵引理，或者直接从简单的描述中使用 Myhill-Nerode 定理。对于抽取引理，选择 1^p 0^p 并论证抽取增加了太多的 1。要使用 Myhill-Nerode，请选择序列 1、11、...、1^k、...，并论证可以附加到 1^k 以得到您的语言中的字符串的最短字符串是 0^k ，意味着所有 1^k 都是可区分的。