Question

1. The decimal notation for a number is the number written in the usual way, as a string over the alphabet {0,1,⋯9}. For example, the decimal notation for 13 is a string of length 2. In unary notation, only the symbol “I” is used; thus 5 would be represented as IIIII in unary notation. Show that each of the following is or is not a regular language.

(For regular languages, write down its regular expression or describe the automata accepting it; for languages that are not regular, prove it using pumping lemma)

1. {w: w is the unary notation for a number that is a multiple of 7}
2. {w: w is the unary notation for 10n,n ≥1}

Answer 1

Both of these are regular languages:

1. {w: w is the unary notation for number that is multiple of 7}

reg expression - (IIIIIII)^* = (I⁷)*

PFA automata image: S is start state and F is the final state. Here both are represented by the same node. Since string of 0 length is also a multiple of 7.

2. {w: w is the unary notation for 10n,n ≥1}

reg expression - (IIIIIIIIII)⁺ = (I¹⁰)⁺

PFA automata image: S is start state and F is the final state