MHB Show that the language is regular

  • Thread starter Thread starter mathmari
  • Start date Start date
  • Tags Tags
    Language Regular
Click For Summary
The language \( C_n \), consisting of binary numbers that are multiples of \( n \), is regular for each \( n \geq 1 \). To demonstrate this, one can construct a non-deterministic finite automaton (NFA) with states representing the possible remainders when dividing by \( n \). As binary digits are read from right to left, the remainder changes based on the current state and the input digit. This approach effectively captures the transition between states corresponding to different remainders. Thus, \( C_n \) can be recognized by an NFA, confirming its regularity.
mathmari
Gold Member
MHB
Messages
4,984
Reaction score
7
Hey! :o

Let $$C_n=\{x \ \mid \ x \text{ is a binary number that is a multiple of } n\}$$

Show that for each $n \geq 1$, the language $C_n$ is regular. Could you give me some hints how we could show that??

Do we have to construct a NFA that accepts the language??
 
Physics news on Phys.org
Let the set of states be $0,\dots,n-1$, i.e., possible remainders when a number is divided by $n$. Think about how the remainder changes when a number is read digit by digit right to left.
 

Thread 'Two interesting number theory tricks'

First trick I learned this one a long time ago and have used it to entertain and amuse young kids. Ask your friend to write down a three-digit number without showing it to you. Then ask him or her to rearrange the digits to form a new three-digit number. After that, write whichever is the larger number above the other number, and then subtract the smaller from the larger, making sure that you don't see any of the numbers. Then ask the young "victim" to tell you any two of the digits of the...
View full post »

Similar threads

MHB Show Closure of Regular Languages: $L_1$ and $L_2$
  • · Replies 6 ·
Replies
6
Views
2K
MHB Is the language ${L}_{n}$ regular?
  • · Replies 3 ·
Replies
3
Views
2K
MHB Show that if K is regular and M any language, then L is regular
  • · Replies 4 ·
Replies
4
Views
2K
MHB Show that the languages are undecidable
  • · Replies 2 ·
Replies
2
Views
2K
MHB Regular and not regular Language
  • · Replies 3 ·
Replies
3
Views
2K
MHB Convert an automaton into a regular expression
  • · Replies 1 ·
Replies
1
Views
2K
MHB Proving Undecidability: Reducing H_0 to H_epsilon
  • · Replies 12 ·
Replies
12
Views
4K
Prove or disprove that chop(L) is a regular language
  • · Replies 1 ·
Replies
1
Views
2K
MHB Finding DFA: Hint to Construct NFA for ((0∪1)*10* ∪ 0)
  • · Replies 43 ·
2
Replies
43
Views
8K
MHB Proving L is not Regular using Pumping Lemma
  • · Replies 1 ·
Replies
1
Views
2K