How many equivalence classes in the RL relation for {w in {a, b}* | (#a(w) mod m) = ((#b(w)+1) mod m)}

debugcn 投稿 Dev

Abraham Murciano Benzadon

How many equivalence classes in the RL relation for

{w in {a, b}* | (#a(w) mod m) = ((#b(w)+1) mod m)}

I am looking at a past test question which gives me the options

m(m+1)
2m
m^2
m^2+1
infinite

However, i claim that its m, and I came up with an automaton that I believe accepts this language which contains 3 states (for m=3).

Am I right?

Patrick87

Actually you're right. To see this, observe that the difference of #a(w) and #b(w), #a(w) - #b(w) modulo m, is all that matters; and there are only m possible values of this difference modulo m. So, m states are always sufficient to accept a language of this form: simply make the state corresponding to the appropriate difference the accepting state.

In your DFA, a2 corresponds to a difference of zero, a1 to a difference of one and a3 to a difference of two.

この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。

侵害の場合は、連絡してください[email protected]

編集2021-06-12

コメントを追加

サインイン

分類Dev

Related 関連記事

記事

How many equivalence classes in the RL relation for {w in {a, b}* | (#a(w) mod m) = ((#b(w)+1) mod m)}

How many equivalence classes in the RL relation for {w in {a, b}* | (#a(w) mod m) = ((#b(w)+1) mod m)}

{w in {a、b} * |のRL関係にある同値類の数 （#a（w）mod m）=（（＃b（w）+1）mod m）}

a ^^ b mod mを計算する方法は？

flask many-to-many-relation leads to "Multiple classes found for path"

awk and equivalence classes

Need to install libapache2-mod-php7.0 if I'm installing PHP7.0 FPM?

Removing Duplicates from sorted LinkedList Relation b/w "slow" and "head"

1 mod3の説明

MOD REWRITE (htaccess) how to rewrite: index.php?lang=$1&pagePL=$2

Algorithm to finding if the numbers in the list, when added or subtracted, are equal to a mod b

How can I make a Many to many relation on same table (many to many Join To Self)

A => M [B]をM [A => B]に変える

L = {（na（w）-nb（w））mod 3> 0}のDFAを構築します

How to check if mod_rewrite is enabled in php?

How to convert sql mod to django orm?

c＃のルール：mod b、aはbより大きい

How to create a one to many relation between models in Ruby on Rails?

Using std algorithm library for unique equivalence with respect to binary relation

Many to many relation and query builder

How many (classes of) objects can YOLO detect?

How to extend many Error classes dynamically?

How to test the equivalence of maps in Golang?

How to test the equivalence of maps in Golang?

w3m保持自动刷新

1行でX Mod Nを増分

How to run mod_mono on Debian Jessie (package libapache2-mod-mono missing)?

Javaでの時間ベースのトークンを解析するには？（1M 1M 1D 1Y 1W 1S）

How to read informats data: $1,000.1M to 1000.1

How remove entry in join table many-to-many relation (ASP. NET)

hibernate how to select the many-side from an one-to-many relation

{w in {a、b} * |のRL関係にある同値類の数（#a（w）mod m）=（（＃b（w）+1）mod m）}