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