Question

CSC 220 Fall 2018 Homework #3 Due at the beginning of the class on December 4th 1. Use a Regular Expression to define the set of all bit strings of one or more 0's 2. 3. Are these two grammars the same? followed by only a 1. Use a Regular Expression to define the set of all bit strings of two or more symbols followed by three or morc 0's. 4. Use process of climination to find the language of the following FA: 0,1 Start 0,1 SO S1 0 5. Let T be the Turing Machine defined by the five tuples: (S0,0,S1,1,R), (S0,1,S1,0,R), (S0,B,S1,0,R), (S1,0,S2,1,L), (S1,1,S1,0,R), (S1,B,S2,0,L). For the following initial step, determine the final tape when T halts, assuming that T begins from the initial position:

1. Use a Regular Expression to define the set of all bit strings of one or more 0's followed by only a 1.

2. Use a Regular Expression to define the set of all bit string of two or more symbols followed by three or more 0's.

3. Are these two grammars the same?

a. S-> aSb|ab|λ

b. S-> aAb|ab A->aAb|λ

4. Use the process of elimination to find the language of the following FA: (see picture for diagram)

5. Let T be the Turing Machine defined by the five tuples: (S0,0,S1,1,R),(S0,1,S1,0,R),(S0,B,S1,0,R),(S1,0,S2,1,L),(S1,1,S1,0,R),(S1,B,S2,0,L). For the following initial step, determine the final tape when T halts, assuming that T begins from the initial position: (see picture for diagram)

Answer 1

1.
0⁺1

2.
(0+1)(0+1)⁺000⁺

3.
Not same
a derives (ab)*
b derives (ab)⁺

4.