Reference no: EM131417211

1a-f) Multiple Choice: Select the best answer and write it on the blank. Also provide the specification for the language.

Which specification technique would be the weakest(least powerful; we talked about the layers of specification power)that is capable of describe this language?

a)  strings of  three or more g's 

A.  regular expression    C.  pseudorational grammar

B.  context free grammar             D.  language expression

b)  expressions consisting only of single digits separated by +  such as      

A.  regular expression    C.  pseudorational grammar

B.  context free grammar             D.  language expression

c)  lists of digits such as

A.  regular expression    C.  pseudorational grammar

B.  context free grammar             D.  language expression

d)  ambn  : strings with m a's followed by n b's  , m, n ≥ 1

A.  regular expression    C.  pseudorational grammar

B.  context free grammar             D.  language expression

e)  anbn  : strings with some number of a's followed by same number of b's  , n ≥ 1

A.  regular expression    C.  pseudorational grammar

B.  context free grammar             D.  language expression

f)  strings of 1's of an even length, containing only 1's

A.  regular expression    C.  pseudorational grammar

B.  context free grammar             D.  language expression

g)  binary strings containing an even number of 1's ( at least one 1 )

A.  regular expression    C.  pseudorational grammar

B.  context free grammar             D.  language expression

2a-l) True or False: Write a T or F in the blank

___ a) Automata is just another name for a graph

___ b) YACC is a tool that is used to build a parser

___ c) It is called a 'finite' state automata because it will only work for finite languages

___ d) The only way to represent an automata is the nodes/edges graphical diagram

___ e) Regular grammar just means that the grammar is correctly written

___ f) A context free grammar is also a regular grammar

___ g) A regular grammar is also a context free grammar

___h) BNF rules are used as the production rules in a context free grammar

___ i) Regular Expression (a | b)(c | d) generates a finite language

___j) RE's (a | b)(c | d) and (c | d)(a | b) denote different languages {set of words}

___ k) RE's (a | b)(c | d) and (b | a)(c | d) denote different languages

___ l) RG's can be used to replace any context free grammar

3) Draw an automaton that recognizes precisely the following language: strings, from the alphabet {a, b}, which contain a substring with at least 2 consecutive b's.

4) Consider the language over alphabet {a, b} that contains all strings that have a length of at least 2 and also start and end with the same letter - for example ( abaa ).  Provide the following for this language (a) Regular Expression  (b) DFA (c) Context Free Grammar [ give the CFG some thought to not make it twice as long as necessary ]

5) For each string, indicate if it will be accepted by the DFA.

String	Yes	No
0 1 0 1
0 1 0 1 0
0 1 1 1 1
0 0 1 0 1

 

 

 

6) Indicate with Yes or No: Is the word in the language defined by the specification rules? Circle Y or N   for each word and each language. (or delete the wrong answer )

Word	Is In A àAa Aà b		Word	Is In ( a | b )*
ab	Y      N		ab	Y      N
aab	Y      N		aab	Y      N
baa	Y      N		baa	Y      N
Word	Is In A àAA Aà ab		Word	Is In (ab)*
ab	Y      N		ab	Y      N
aab	Y      N		aab	Y      N
baa	Y      N		baa	Y      N
Word	Is In A àa B Bàb | x | a		Word	Is In a*b*
ab	Y      N		ab	Y      N
aab	Y      N		aab	Y      N
baa	Y      N		baa	Y      N

7a-b) Consider a language of all nonempty sequences of @ symbols.

a) Write a regular expression for this language

b) Write a context free grammar for this language

8) Draw a parse tree for aaa as produced by grammars G3 and then G4.

Grammar : G3		Grammar : G4
S = a S S = a		S = S a S = a

9 a-b) Consider our standard Expression grammar as a guide for correctly formed expressions.

1) E = E + T

2) E = T

3) T = T * F

4) T = F

5) F = (E)

6) F = num

a) Draw a Parse Tree for the expression for     2 + (5 + 3) * 7

b) Draw an Abstract Syntax Tree for the same expression

c) Show the infix, prefix, and postfix representation for the expression from (a)

10) Lex & YACC implementation. Below include Lex & YACC specification as well as sample output. You can just paste the text of the Lex/YACC/Output rather than screen shots Format it, make it readable. Also indicate the location in account for the code. Sample output to right (15 pts)

Problem: read in a list of numbers; report back the sum & count

• space separated list of positive integers
• may be more than 1 digit in a number

Attachment:- Assignment.rar