SRM University 2007 B.Tech Computer Science and Engineering BANK : COMPILER DESIGN - Question Paper

TWO MARKS:

01. elaborate the capabalities of CFG?
02. describe regular expressions.
03. describe a finite state automation.
04. Draw the NFA for a*b*.
05. What is a transition diagram? provide example.
06. What is a recogniser?
07. what is CFG? provide example.
08. define language denoted by the subsequent regular expression:
0(0/1)*0
09. define language denoted by the subsequent regular expression:
(0/1)*0(0/1)(0/1)
10. define language denoted by the subsequent regular expression:
(00/11)*((01/10)(00/11)*(01/10)(01/10)(00/11)*)*
11. define language denoted by the subsequent regular expression:
0*a0*a0*a0*
12. Write the regular definition for the subsequent language:
"All strings of digits with no repeated digits"
13. provide an example for ambiguous grammar and justify it.
14. What is a parse tree?
15. Consider the grammar:
S --> (L)/a
L --> L,S/S
elaborate the terminals, non-terminals and begin symbols?
16. Differentiate NFA and DFA.
17. elaborate the kinds of derivation?
18. What is right-most derivation? provide example.
19. What is left-most derivation? provide example.
20. discuss canonical derivations.
21. What is left-sentential form?
22. What is right-sentential form?
23. What is sentence of a grammar G?
24. What is Context-Free Language?
25. What is regular definition? provide example.
26. Write the algorithm for simulation of DFA.
27. What is a non-regular set?




28. Minimise the provided transition table:
states a b
A B C
B B D
C B C
D B E
E B C
Initial State=A Final State=E
29. Write regular definition for a number which can have fraction or exponent part as optional.
30. For the subsequent grammar:
list --> list+digit / list-digit / digit
digit --> 0/1/......../9
Derive the sentence (9+5-4) using left-most derivation.


















UNIT 2

TEN MARKS:

01. Write notes on:
(i) Regular expressions.
(ii) situation Free Grammar.

Earning:   Approval pending.