Question

This question deals with NFAs, DFAs, and regular expressions.

1. (a) Using only the symbols described in the lecture slides, write a regular expression that describes all strings over the alphabet Σ = {0,1} that are at are at least four bits long and begin and end with the same bit.

2. (b) Draw a DFA, that accepts strings strings over the alphabet Σ = {0, 1} such that if you read the string from left to right, the difference between the number of 0s and 1s read up to any point in the string is never more than 2. For example, 10100111 and the ε (the empty string) would be accepted. However, 111000 would be rejected because it starts with 3 occurrences of a 1 before seeing a 0, and 01001101001001 would be rejected because when reading the last 0 in the string, that is the 8th occurrence of a 0 and only the 5th occurrence of a 1 at that point. The difference in this case is 3.

   Your solution must read all bits from the string. In other words, each state in the DFA must have a transition labelled with a 0 and a transition labelled with a 1.

3. (c) Draw a finite state machine, either a DFA or an NFA, over the alphabet strings over the alphabet Σ = {a, b, c} that matches this regular expression:

                                (a|b)* c a? b? c+ (a*|b*)
   

   Note that there are no spaces in this alphabet. The spaces are included in the regular expression for readability. Also, you are not required to read a whole string that would be rejected. In other words, a correct solution may contain states that do not have transitions for all possible inputs.

Answer 1

Dale

thankyou