在E = {a，b}上找到该语言的正则表达式 [英] Find the regular expression for the language on E={a,b}

问题描述

L = w:(na(w)-nb(w))mod 3/= 0

L = w : (na(w) - nb(w)) mod 3 /= 0

如何找到该语言的正则表达式?

How can I go about finding the regular expression for this language?

我了解这意味着As的数量减去B的数量不能为3的倍数.所以a-b不能为3、6、9、12等.

I understand that it means that the number of As minus the number of Bs cannot be a multiple of 3. So a - b cannot be 3,6,9,12, etc.

但是我仍然很难将其放入正则表达式中.我先尝试将其设置为DFA或NFA，但我也无法做到这一点.

But I am still having trouble putting it into a regular expression. I tried first making it a DFA or NFA but I couldn't do that either.

感谢您的帮助！

推荐答案

我会通过将{a，b}上的单词列表分为三种情况来解决此问题:

I would go about it by dividing the list of words on {a,b} into three cases:

• L1 = w:(na(w)-nb(w))mod 3 = 1
• L2 = w:(na(w)-nb(w))mod 3 = 2
• L3 = w:(na(w)-nb(w))mod 3 = 3

L为L1 U L2，您应该能够创建与L1，L2和L3相关的表达式.然后，您应该可以消除问题并在{a，b}上使用正则表达式结束.

L is then L1 U L2, and you should be able to create expressions relating L1, L2, and L3. You should then be able to eliminate things and end up with a regular expression on {a,b}.

这篇关于在E = {a，b}上找到该语言的正则表达式的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！