Note (please a give a detailed and simplified explanation like your teaching a k

Question

Note (please a give a detailed and simplified explanation like your teaching a kid. Explantion should be precise not too long or too short. Please please just don't quote bunch of book definations because i have gone through all of them)

So i'm trying to understand if the language is regular or not. so i assume L is a proper subset of alphabet kleenstar. which means L ={0,1,.....9}*?(is it correct)

why we used 0U sigma*

why we are using intersection for L2

L3 = sum of numbers divisible by 3. i got upto there but how we know which set of number goes with wich state because all set of numbers are divisible by 3 and 2 both.

Then remainder is 0 for all of them. I thoght that might be we will take set of numbers and if remainder is 0 the set of number will go on that arrow. but it's working differently.

Example 2.4.1: Let = {0,1, ,9) and let L C be the set of decimal representations for nonnegative integers (without redundant leading 0's) divisible by 2 or 3. For example, 0,3,6, 244e L, but l ,03, 00 L. Then L is regular. We break the proof into four parts. Let Li be the set of decimal representations of nonnegative integers. Then it is easy to see that which is regular since it is denoted by a regular expression. Let L2 be the set of decimal representations of nonnegative integers divisible by 2. Then L2 is just the set of members of L, ending in 0, 2, 4, 6, or 8; that is, la-L1 n "(0, 2, 4, 6, 8), which is regular by Theorem 2.3.1(e) Let Ls be the set of decimal representations of nonnegative integers divisible by 3. Recall that a number is divisible by 3 if and only if the sum of its digits is divisible by 3. We construct a finite automaton that keeps track in its finite control of the sum modulo 3 of a string of digits. Ls will then be the intersection

Explanation / Answer

As per my understanding, you are trying to ask, that given an integer number, how to find if it is divisible by 2 or 3 using the state diagram.

Let us take an example to understand this. given the state diagram fig 2.18, to find if a number is divisible by 3 or not.

Let us take a number 15756 since the sum of digits is divisible by 3 here, the number is also divisible by 3. Now let us check this using the state diagram given in fig 2.18,

0,1 and 2 are three states, where 0 is the initial state. that means initially we are at state 0, when we see 1 from 15756, in the state diagram, the arrow moves to state 1 on seeing 1,4,7, thus we reached state 1 on reading 1 from 15756. Next, we read 5, on seeing a 5 in the state diagram, the arrow points back to state 0, thus we reached state 0 again.

The next number we read in 15756 is 7, from state 0, on seeing a 7, the arrow moves to state 1 again.

next number to read in 15756 is 5, from state 1, reading a 5, array moves to state 0 again,

At last reading a 6 in 15756, we can see in the state diagram that, there is a self-loop in state 0, on seeing 0,3,6,9. Thus on seeing 6, the arrow points to itself, i.e it remains at state 0 only.

Now we don't have any number to read, and we have reached state 0, which is an accepting state (Note that an accepting state is represented by a double circle, here it state 0). An accepting state means that the number is divisible by 3.

Do comment below, if I am wrong in understanding your last question.

Related Questions

Navigate

• Browse (All)
• Browse N
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.