Automata and compiler, Theory of Computation

Assignment Help:

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


Related Discussions:- Automata and compiler

Numerical integration, what problems are tackled under numerical integratio...

what problems are tackled under numerical integration

Non-regular languages, Suppose A = (Q,Σ, T, q 0 , F) is a DFA and that Q = ...

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

Finiteness problem for regular languages, The fact that the Recognition Pro...

The fact that the Recognition Problem is decidable gives us another algorithm for deciding Emptiness. The pumping lemma tells us that if every string x ∈ L(A) which has length grea

Non-determinism - recognizable language, Our DFAs are required to have exac...

Our DFAs are required to have exactly one edge incident from each state for each input symbol so there is a unique next state for every current state and input symbol. Thus, the ne

Transition graphs, We represented SLk automata as Myhill graphs, directed g...

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

Myhill graph of the automaton, Exercise:  Give a construction that converts...

Exercise:  Give a construction that converts a strictly 2-local automaton for a language L into one that recognizes the language L r . Justify the correctness of your construction.

Sketch an algorithm for recognizing language, Suppose A = (Σ, T) is an SL 2...

Suppose A = (Σ, T) is an SL 2 automaton. Sketch an algorithm for recognizing L(A) by, in essence, implementing the automaton. Your algorithm should work with the particular automa

IT PRoject Management, What are the benefits of using work breakdown struct...

What are the benefits of using work breakdown structure, Project Management

Kleene closure, So we have that every language that can be constructed from...

So we have that every language that can be constructed from SL languages using Boolean operations and concatenation (that is, every language in LTO) is recognizable but there are r

Decision problems, In Exercise 9 you showed that the recognition problem an...

In Exercise 9 you showed that the recognition problem and universal recognition problem for SL2 are decidable. We can use the structure of Myhill graphs to show that other problems

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd