PROG24310 Programming Languages

Problem N1

You have the following context-free gramma:

S -> AB
B -> bAaAB | a
A -> Ab |

Using the grammar above and a right-most derivation, is it possible to obtain a string “babbabbabba” ?

If so, please provide the derivation process and build the abstract syntax tree. Is this grammar ambiguous? If so, please provide a different abstract syntax tree for another right-most derivation that will produce the same string.

Requirements: the derivation must be canonical (right-most). You must show every step of the derivation process and use brackets [] for the next symbol you are replacing. Example: S -> A[B] means on the next step you will be replacing symbol B.

Problem N2

Write a regular expression that can match a string that starts with a digit (i.e. 0-9). and contains substrings ab or cd followed by at least 3 but no more than 5 digits. The string cannot end with such a substring! The match should be case sensitive. For example, the following strings are valid: 1Ghab345c, 22Zui2cd777@ String ab345c is incorrect, because it doesn’t start with a digit.

 

String 1Ghab345 is incorrect because it ends with a matching substring.
String 1Ghab345678 is incorrect because more than 6 digits follow substring ab.
String 1GhAb345c is incorrect because A is upper case.
Note: strings 11ab345ab345c, 1ab345aab345c are correct and have two substrings.

Problem N3

For certain values of float a and float b, expressions (a + b)*10 and a*10 + b*10 can differ by more than 20% even when both a and b are of the same magnitude. Please provide a program in C with fixed variables a and b that confirm this claim. You must prove the statement above without going out of bounds! I.e. a*10 or b*10 or (a+b)*10 should never exceed the max/min floating-point value. Your program should have NO input from the user. I.e. in your program you’ll have float a=..some value..; Demo run:

Requirements: your solution must match the demo run. Values a and b must be of the same magnitude and not extreme (i.e. should not be too small or too big).