Theory of Computer Science:

Question 1: Regular Languages (6 Marks) Argue that each of the following languages are regular by showing how to construct it using the definition of regular languages:

a. (2 marks) The language of all binary strings of odd length.

b. (2 marks) The language of strings over the alphabet {a,b,c} in which every b is immediately followed by two cs. The string acbccbccbccaacccbcccbcc is in this language because every b is followed by two cs (more than two is fine; there just have to be two cs immediately after the b). The string accacccbcc is not in this language because the highlighted occurrence of b is followed by only one c.

c. (2 marks) The language of all binary strings with an even number of 0s or a number of 1s that is divisible by 4. The strings 0110011101010, 001100110111001, and 1011001101100100 belong to this language: 0110011101010 contains an even number of 0s, 001100110111001 contains a number of 1s divisible by 4, and 1011001101100100 satisfies both conditions. The string 001101001100 is not in this language because it contains an odd number of 0s and the number of 1s is not divisible by 4.

Example: The language of all strings over the alphabet {a, b, c} that contain the substring aaa is regular: We start with our base cases: The languages {a}, {b}, and {c} are regular. This implies that the language {aaa} = {a}{a}{a} is regular, as is the language {a,b,c} = {a} U {b} U{c}\). The latter implies that {a,b,c}* is regular. Therefore, the language {a,b,c}*{aaa}{a,b,c}* is regular. But this is exactly the desired language because any string in this language consists of an arbitrary number of letters, followed by the substring aaa, followed by another group of an arbitrary number of letters, that is, it contains the substring aaa.