Consider the (decimal) languages defined below. For each one, either give a regu

Question

Consider the (decimal) languages defined below. For each one, either give a regular expression for its elements or prove the language is non-regular:

In all examples, a number cannot start with a 0 (unless it is 0 itself):
a) La = { w | as an integer w is a multiple of 25 }.
b) Lb = { w | as an integer w is a multiple of 10 }.
c) Lc = { w | as an integer w is a power of 10 }.
d) Ld = { w | as an integer w is a multiple of 2 }.
e) Le = { w | as an integer w is such that the sum of its digits is a multiple of 2 }.
f) Lf = { w | as an integer w is a power of 2 }.
g) Lg = { w | as an integer } (with SUM = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, -}).
h) Lh = { w | w is the decimal representation of a rational number}. (with SUM = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, -, ., [,]}) Examples of such strings are 0.[3] representing the number 0.3333...=1/3 and -23.15[24] representing the number -23.152424242424...=-76403/3300.

Explanation / Answer

Hi,
Answering the 1st 4 sub parts as per chegg policy, please post others as separate question.
1.Multiple of 25 i.e 25,50,75,100,125,150..
i.e all numbers ending with 00,25,50,75 are divisible hence RE will be
^[1-9][0-9]*[25,50,75,00]$
2.Multiple of 10,
we know that every multiple of 10 must end with 0, hence the RE will be ^[1-9]+[0-9]*0$
which means it can start with any of the 1-9 digits and can have any number of digits in between but should have 0 at end.
3.power of 10 i.e 10, 100, 1000.. as you can see, the first digit should be 1 and there can be any number of 0's following it so RE will be ^1[0]*$ , here * means 0 or more, since 1 is also 10^0

4.multiples of 2 i.e 2,4,6,8,10,12,14..
if you notice the pattern, the numbers always end with 2,4,6,8 or 0 , so the RE will be
^[1-9][0-9]*[2,4,6,8,0]$
Thumbs up if this was helpful, otherwise let me know in comments

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

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