Question

4. Construct regular expressions for the following languages over the alphabet {a, b}: a. Strings that do not begin with an “a”.

b. Strings that contain both aa and bb as substrings.

5. Let ? = {? ?? ?? ? | ? > ? + ?}. a. List all strings of length 7. (use power notation: i.e. aabbbbaaaaaaaa is a2b 4a 8 )

b. Use the Pumping Lemma for Regular Languages to prove that L is not regular.

Answer 1

4.a) Given,

Since the string should not be starting with an "a",
Therefore, it must start with a "b" and after wich it can have
any number of a or b.

so the regular expersion will be

4.b)
Since the string should contain "aa" and "bb" as its substring,
so it can start with either "a" or "b".

5.a).

There will be 5 distinct string of length exactly equal to 7.

String	n	l	k
bbaaaaa	0	2	5
bbbaaaa	0	3	4
abbaaaa	1	2	4
aabaaaa	2	1	4
aaaaaaa	2	0	5
aaaaaaa	3	0	4

You see that the last two string are same, therefore total 5 distinct strings.

5.b) To prove L is not regular by using Pumping Lemma.

Let us assume L is regular,

then there will be  w such that

let w = aabbbbaaaaaaaa.

consider x = aa, y =bbbb, z = aaaaaaaa.

Now for any i,

Let i =2

then .

which gives n =2, l =8, k =8.

This will contradict the fact that n+l < k.

Hence, language L is not a regular.