1. Draw a non-deterministic finite automaton which accepts the language denoted by the regular expression
(0 + 1)∗0101∗
4. If L = {10, 100} and M = {01, 1, 100} are languages on the alphabet {0, 1}, then write down the values of (i) LM and (ii) L + M.
6. Show that the grammar below (written with BNF notation) is ambiguous.
< Program > ::= < Stmt > | < Program > ; < Stmt > < Conditional > ::= if < Bool > then < Program >
< Bool > ::= true | false
<Stmt> ::=<Conditional>|S1 |S2
Parse trees can be used to give meaning to words in context free languages. Use your example to give two different meanings to a word in this grammar.
The approximate number of marks to be assigned to these questions are, in order, 3, 5, 2, 2, 2, 6, making 20 in total.