Question

Formal Languages

Give a regular expression for each of the following languages:
L2a = {w ? {0,1}* | w corresponds to the binary encoding of non-negative integers that are evenly divisible by 4
L2b = {w ? {a,b}* | w contains at least one 'a' and exactly two b's}
L2c = {w ? {0, 1, 2}* | w starts with a 2, ends with a 1 and contains an even number of 0's}.

Answer 1

See when you are trying to make a regular expression you want to see things with your result. First, it should be able to accept all the strings that you want to accept, and second, it should not accept any unwanted strings. Understood, now let's try to make some regular expressions.

a) {w '∈ {0,1}* | w corresponds to the binary encoding of non-negative integers that are evenly divisible by 4}

This is easy we just need to understand what it means. See when we are writing binary no.'s each bit is assigned a value. The assigned values are as follows (from LSB to MSB):-

1, 2, 4, 8 , 16, 32, 64, .....

See just the least two values, i.e., 1 & 2 are the values that are not divisible by 4 rest all the values are divisible by 4. So if we want our no.'s to be divisible by 4 we need to make those two bits 0. So we can say that we need to accept all the strings that end with two 0's. Before that, we can accept anything.

So the regular expression will be:-

(1+0)*00

b) {w ? {a,b}* | w contains at least one 'a' and exactly two b's}

w is supposed to contain exactly 2 b's so we need to fix that, but the no. of a's only have the lower limit that is it should have at least one a.

When stuck try making the smallest strings with some other strings that you want to accept through your regular expression, or you can also try making the DFA for the language.\

The regular expression will look like this:-

a(a*ba*ba*) + b (ba + aa*b)a*

c) {w ? {0, 1, 2}* | w starts with a 2, ends with a 1 and contains an even number of 0's}

This one is easy again.

2(00)*1

Hope this helps. If you like the answer please upvote. If you have any queries or suggestions regarding the answers please leave them in the comments section so I can update and improve the answer. Thank you