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
We will assume that the string has been augmented by marking the beginning and the end with the symbols ‘?' and ‘?' respectively and that these symbols do not occur in the input al

Suppose A = (Q,Σ, T, q 0 , F) is a DFA and that Q = {q 0 , q 1 , . . . , q n-1 } includes n states. Thinking of the automaton in terms of its transition graph, a string x is recogn


Another way of interpreting a strictly local automaton is as a generator: a mechanism for building strings which is restricted to building all and only the automaton as an inexh

Theorem (Myhill-Nerode) A language L ⊆ Σ is recognizable iff ≡L partitions Σ* into ?nitely many Nerode equivalence classes. Proof: For the "only if" direction (that every recogn

What is the purpose of GDTR?

1. Simulate a TM with infinite tape on both ends using a two-track TM with finite storage 2. Prove the following language is non-Turing recognizable using the diagnolization

Applying the pumping lemma is not fundamentally di?erent than applying (general) su?x substitution closure or the non-counting property. The pumping lemma is a little more complica

Paths leading to regions B, C and E are paths which have not yet seen aa. Those leading to region B and E end in a, with those leading to E having seen ba and those leading to B no