Question

3 points) Question Three Consider the context-free grammar S >SS+1 SS 1a and the string aa Give a leftmost derivation for the string. 3 points) (4 poiots) (5 points) (3 points) sECTION IWOLAttcmpt.any 3.(or 2) questions from this.scction Suppose we have two tokens: (1) the keyword if, and (2) id-entifiers, which are strings of letters other than if. Show the DFA for these tokens. Give a nightmost derivation for the string. Give a parse tree for the string i) Is the grammar ambiguous or unambiguous? Justify your answer. v) Describe the language generated by this grammar. (7 points) b (5 points) Consider the following regular expression: (a | b) a (a 1 b) Construct an NFA for this expression using Thempuon's Method Disprove or support the statement that says CFG is more powerful than RE by using any suitable language. Identifiers formed as follows: an identifier consists of one or more letters (a-z and A-Z), digits (0-9) (7 points) Question Four (4 points) 2.Def b. Using the Subset Constrwtion method, build the corresponding DFA for this expression. Take care to label aC (6 points) start and accept states. (clearly show how you arrived at your state diagram) b Des (This notations might be helpful - character (...) and [...), concatenation (xy), alternation (x | y), repetition (x and x+), and optional (x?) Defa d Write a d. Write a context free grammar for the strings that consist of equal number of a's followed by cqual number of b's. 3Write a C++F and underscores (). An identifier must begin with a letter and may not end with an underscore. Express using a regular expression. and print the lar) enter the item co The output will lo Enter item no Enter item code (3 points) this case Write out the regular expression for this language: All strings of p's and q's starting and ending with (6 points) Enter item Price (3 points) in Menu play Largest Price ay Sum of Prices (5 points) Question Five Item List a b. Draw the DFA to represent the RE in (a) above n in C++ to find we are going ion named get Briefly explain the relationship between an activation tree and activation record. c. int fint n) int t, s will return total if (n < 2) return 1; f(n-1); t= f(n-2); o keep calct he user will return s+t; 2-1+2 Consider the above code snippet. Assume that the initial call is f(5), draw the activation tree.

Answer 1

question 3 :

Given

SSSSS a

and the String is aa+a*

a (answer): GIve the Leftmost Derivation for the String

The following is the leftmost derivative of the String

S$\Rightarrow$SS*

$\Rightarrow$ SS+S*

  $\Rightarrow$aS+S*

$\Rightarrow$aa+a*

b.(answer) Give the Right most derivation for the String

The rightmost derivation for the String is

S$\Rightarrow$SS*

  $\Rightarrow$Sa*

  $\Rightarrow$SS+a*

  $\Rightarrow$Sa+a*

  $\Rightarrow$ aa+a*

c.(answer)Give the Phase Tree for the String

S

                                   S       S         *

                                                                                                                                                                                                            

                                                                                                                                                                                                             S S +   a

                            

                                         a     a

d(answer).

here the grammer is unambiguous, the postfix expression consists of all plus and multiply symbols i.e., addition and multiplication language.