Automata and compiler, Theory of Computation

Automata and Compiler

(1) [25 marks] Let N be the last two digits of your student number. Design a finite automaton that accepts the language of strings that end with the last four bits of the binary expansion of N. (1.1) Make a regular expression ? of this language. For example the set of strings that end with 101 is expressed by a regular expression (0+1)*101. (1.2) Make an NFA that accepts this expression ?. You should remove any ?-moves that can be done trivially by inspection. (1.3) Make a subset automaton that accepts the language. (1.4) Perform state minimization on the above automaton.

(2) [25 marks] A CFG is given by S ? aSbS, S ? bSaS, S ? c

(2.1) Draw a syntax chart for this grammar. [5]

(2.2) Write a Python program for the recursive descent parser Trace the parser using two strings of at least 10 symbols, one for an accepted case and one for an unaccepted case. Do the trace using the style in the notes. [20]

(3) [25 marks] A sample program for computing the greatest common divisor by recursive call and its object program are given below. Some sample comments are given.

const a=75, b=55;

var x, y;

procedure gcd;

var w;

begin

if y>0 then begin

w:=y;

y:=x ? (x/y)*y;

x:=w;

call gcd;

end;

end;

begin

x:=a; y:=b;

call gcd;

write(x);

end.

0 jmp 0 21 Jump to 21, start of main

1 jmp 0 2

2 inc 0 4

3 lod 1 4

4 lit 0 0 Load literal 0

5 opr 0 12 Test if y>0

6 jpc 0 20 Jump to 20 if false

7 lod 1 4 Load y

8 sto 0 3 Store in w

9 lod 1 3

10 lod 1 3

11 lod 1 4

12 opr 0 5

13 lod 1 4

14 opr 0 4

15 opr 0 3

16 sto 1 4

17 lod 0 3

18 sto 1 3

19 cal 1 2

20 opr 0 0

21 inc 0 5

22 lit 0 75

23 sto 0 3

24 lit 0 55

25 sto 0 4

26 cal 0 2

27 lod 0 3

28 wrt 0 0 Write stack top

29 opr 0 0

Posted Date: 7/21/2012 11:19:01 AM | Location : United States







Related Discussions:- Automata and compiler, Assignment Help, Ask Question on Automata and compiler, Get Answer, Expert's Help, Automata and compiler Discussions

Write discussion on Automata and compiler
Your posts are moderated
Related Questions
automata of atm machine

A common approach in solving problems is to transform them to different problems, solve the new ones, and derive the solutions for the original problems from those for the new ones

how to write program Minimum Cost Calculation - Vogel Approximation Method(VAM

Computer has a single LIFO stack containing ?xed precision unsigned integers (so each integer is subject to over?ow problems) but which has unbounded depth (so the stack itself nev


One might assume that non-closure under concatenation would imply non closure under both Kleene- and positive closure, since the concatenation of a language with itself is included

c program to convert dfa to re



We represented SLk automata as Myhill graphs, directed graphs in which the nodes were labeled with (k-1)-factors of alphabet symbols (along with a node labeled ‘?' and one labeled