CS 311 02 Formal Languages and Automata Homework 2 Complete Solution

Question: #946

CS 311-02 Formal Languages and Automata

Homework #2

1. Construct a NFSA with at least one -moves to accept each of the following languages.
(a) {w{0,1}* | w corresponds to the binary encoding of a positive integer that is
divisible by 16 or is odd}.
(b) {anbam | m, n 0 and n%3 = m%3} For instance, b, aba, aabaa, aaab, abaaaa,aaaaabaa are in the language, but abaa is not.

2. Given M1 = ({1,2,3,4,5,6}, {a,b}, , 1, {6}), where is defined as follows.
(a) Give a computation tree on M1 for string aab. Is aabL(M1)?
(b) Find the equivalent NFSA M2 without -moves for M1.
(c) Give a computation tree on M2 for string aab. Is aabL(M2)?
M1
1
2
3
4
5
6

2
4
1

a
3
2
5
-

b
4
3
6
-

3. Find a REGULAR EXPRESSION corresponding to each of the following.
(a) { w{a,b}* | #a(w) 3 }.
(b) { anbm | n+m is even, where n, m 0 }.
(c) { x{0,1}* | x has no two consecutive 0s and no two consecutive 1s }.
(d) All binary strings whose value are greater than or equal to 32.
(e) The set of all signed or unsigned integers and real numbers in decimal notation. No leading zeros should be generated and real numbers must have at least one digit on both sides of the decimal point. For instance, 3, +3, -3, 0, +0, -0, 0.328, 1009.46, +100.80, and-100.3 are in the language, but 123., .25, +, -, 003 are not.

4. Use the state elimination algorithm (eliminate state A first, then B, then C) to find the regular expression for the language described by M = ({A,B,C}, {0,1}, , A, {B,C}), where is defined as follows. Show steps and do not simply your result.
M
A
B
C

0
B
A
B

1
C
C
A

5. Using the algorithm given in class, construct a NFSA with -moves equivalent to the regular expression (a+b)((a+bab)*+ba*)*. Do not simplify any intermediate steps and the resulting diagram.