Interesting Problem 3 : Decimal to Floating Point Conversion

1. Assuming your not restricted to using normalized form, list all the bit patterns that could be used to represent the value 3/8 using the floating- point format described in Figure contains an 8 bit floating point format "a 1 bit sign bit, b. 3 bit exponent, and c. 4 bit mantissa" A= Sign bit, B= Exponent, C=Mantissa. A B B B C C C C. One of the answers is: 01000110,

My solution:

As stated in the question one of the solutions is 01000110.

So assuming this is the first representation of 3/8 in floating –point format.

3/8 can be written as 0.011 in binary having decimal and integer part.

01000110 is 0110.0 × 2^-4

So other solutions will be

01000011 is 0011.0 × 2^-3

01100001

01110000

The last two solutions are not precise due to fewer bits in Mantissa. This is the limitation of floating point numbers. Preciseness can be improve by having representation in more bits .

Interesting Problem 2 : Pumping Lemma

1. Show that the language {an bcba2n : n ≥ 0} is not regular using the pumping lemma.

Ans. If the Language L = an bcba2n is regular than it can be converted into string w where w = xyz . so we have that xyz = an bcba2n . Now since y ≠ € , there can be three cases .

Case 1 : Now assume y is having an instance of a and z will have the rest of bcba2n . Now according to pumping lemma we will have xyⁱz where i ≥ 0 , will also lies in L but if i = k , then we can increase the instances of a without increasing the instance of a present in substring z . So it can’t be a regular language .

Case 2: Now assume that y = bcb , in that case . xyⁱz when i = 0 will not have any instance of bcb . so the resulting language would be falling in L . Hence L can’t be a regular language.

Case 3: Now assume that y is having an instance of a present after bcb . in that case x = aⁿbcb , y = a^k , z = a^2n-k . Now according to pumping lemma xyⁱz where i≥0 , should lie in L . Now if we increase the value of i , we can have more instances of a in the later part which violates the property of L having exactly double number of instances of a present in the substring x . Hence L can’t be a regular language.

As none of the case is able to provide valid proof of pumping lemma L can’t be a regular language.

Interesting Problem 1 : State Transition Diagram

Give a transition diagram for a pushdown automaton that accepts the language {a^i b^j c^k | i + k = j}.

My Solution :