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

Non Regular, Prove that Language is non regular TRailing count={aa ba aaaa...

Prove that Language is non regular TRailing count={aa ba aaaa abaa baaa bbaa aaaaaa aabaaa abaaaa..... 1) Pumping Lemma 2)Myhill nerode

Convert chomsky normal form into binary form, Suppose G = (N, Σ, P, S) is a...

Suppose G = (N, Σ, P, S) is a reduced grammar (we can certainly reduce G if we haven't already). Our algorithm is as follows: 1. Define maxrhs(G) to be the maximum length of the

Formal language theory, This was one of the ?rst substantial theorems of Fo...

This was one of the ?rst substantial theorems of Formal Language Theory. It's maybe not too surprising to us, as we have already seen a similar equivalence between LTO and SF. But

Closure properties to prove regularity, The fact that regular languages are...

The fact that regular languages are closed under Boolean operations simpli?es the process of establishing regularity of languages; in essence we can augment the regular operations

Two-tape turing machine, Let there L1 and L2 . We show that L1 ∩ L2 is CFG ...

Let there L1 and L2 . We show that L1 ∩ L2 is CFG . Let M1 be a decider for L1 and M2 be a decider for L2 . Consider a 2-tape TM M: "On input x: 1. copy x on the second

Myhill-nerode, Theorem (Myhill-Nerode) A language L ⊆ Σ is recognizable iff...

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

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

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

Decidability, examples of decidable problems

examples of decidable problems

Decision problems of regular languages, We'll close our consideration of re...

We'll close our consideration of regular languages by looking at whether (certain) problems about regular languages are algorithmically decidable.

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