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

a.

La={(1+2+3+4+5+6+7+8+9)* 0*(25+50+75+00) }

b.

Lb={(1+2+3+4+5+6+7+8+9)* 0 }

c.

Lc={10(0)*}

d.

Ld={(1+2+3+4+5+6+7+8+9)*(0+2+4+6+8)}

e.

Le={ (((1+3+5+7+9)(1+3+5+7+9))* +(0+2+4+6+8))* }

f,g,h are non regular languages.

Lf,Lg,Lh are not satisfying closure properties of regular languages.

concatination of regular language is regular, but these are not satisfying these properties so not regular

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

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