The problem is in Ocaml programing language.
Assignment 2 1 Deterministic Infinite Automata (25 points) In class, we’ve studied Deterministic and Nondeterministic Finite Automata, called that because they have a finite number of states. What if we allow deterministic automata to have an infinite number of states, but don’t change anything else? This gives us Deterministic Infinite Automata, or DIAs. For simplicity, we’ll represent these states using integers Z (including negative numbers, zero, and positive numbers). We’ll assume the start state is 0. That just leaves three things to specify about a DIA: • The alphabet Σ • A set of accepting states F ⊂ Z • A transition function δ : Z × Σ → Z Because there are an infinite number of states, we can’t use a normal transition diagram or table to represent the transition function, but we can use a modified transition table that specifies the function like a piecewise function in math. We let n represent the current state. For example, for an alphabet Σ = {a, b}, the table a b n < 0 n n n = 2a, a ≥ 0 n + 1 −1 n = 2a + 1, a ≥ 0 −1 n + 1 means “if in a negative state, stay in that state regardless of input; if in a positive even state, increment by one on an a and go to state −1 on a b; if in a positive odd state, go to state −1 on an a and increment by one on a b.” note that the −1 entries in the table mean “go to the state −1” and not “go to state n − 1 (decrement by one)”. also note that, despite its compact representation, the transition function described is total, that is, it has exactly one entry for each symbol and every possible value of n. in describing dias in this question, you don’t need to use exactly this format for describing transition functions, but make sure that your description is mathematically precise and it’s clear what you mean. (a) (3 points) assume that the above transition table is for a dia with accepting states f = {2a | a ∈ z, a ≥ 0}, that is, the positive even integers. give a regular expression (using only the standard syntax elements: a, b, ϵ, |, ∗ and concatenation) that accepts the same language as the above dia. (b) (3 points) assume that the above transition table is for a dia with accepting states f = {2a + 1 | a ∈ z, a ≥ 0}, that is, the positive odd integers. give a regular expression (using only the standard syntax elements: a, b, ϵ, |, ∗ and concatenation) that accepts the same language as the above dia. (c) (6 points) as it happens, dfas are a special case of dias. describe a procedure for turning any dfa into a dia that recognizes the same language. for simplicity, assume the dfa is described by a (finite) set of states s represented by consecutive nonnegative integers (0 through |s| − 1), and the start state s0 is 0. include how to construct the three necessary features of the dia: the alphabet, the set of accepting states, and the transition function. make sure your transition function is total, as defined above (if it is not, your automaton is not deterministic!) on the other hand, it is not the case that every dia can be turned into a dfa: dias are considerably more powerful. consider the language over the alphabet σ = {a, b}, consisting of strings with the same number of as and bs (but in any order). examples of strings in this language are ϵ, ab, ba, abbbabaa. (d) (3 points) explain in a short paragraph why this language is not regular, that is, why it cannot be represented by a regular expression or recognized by an nfa or dfa. you do not need to give a formal proof. (e) (4 points) construct a dia that accepts exactly the strings in the language over the alpha- bet σ = {a, b} described above. make sure to specify the set of accepting states and a total transition function. now consider the language over the alphabet σ = {(, )} consisting of only strings with correctly matched parentheses. this language is defined by the following grammar: p → ϵ | p p | (p ) as we saw in class, it is not possible to construct a dfa or nfa to recognize this language. (f) (6 points) construct a dia that accepts exactly the strings in the language over the alpha- bet σ = {(, )} described above. make sure to specify the set of accepting states and a total transition function. 2 right recursion (12 points) a grammar is right-recursive if a nonterminal a has a production a → αb such that b ⇒∗ a. a special case is immediate right recusion, where there is a production a → αa. for example, the following grammar is right recursive because of the immediate right recursion in nonterminal a. s → a a → cca | dba | a b → c | b c → c | d (a) (4 points) explain briefly why d ∈ follow(b). (b) (4 points) suppose that, using the above grammar, s ⇒∗ s1s2 . . . sn and s1, . . . , sn are all terminals (that is, s1s2 . . . sn is a sentence of s). what are the possible terminals that sn could be (that is, what could be the last terminal in a sentence derived from s)? (c) (4 points) we know that left recursion causes problems in top-down parsing. since bottom-up (lr) parsing is basically the reverse of top-down parsing, you might think that would mean we can’t use right-recursive grammars in bottom-up parsing. in fact, this actually isn’t a problem. explain why in a short-ish paragraph. 3 ;; (13 points) consider the following fragment of a grammar for ocaml: optrec → rec | ϵ ident → [a − z][a − z, a − z, 0 − 9, ,r ]∗ idents → ident | ident idents expr → ident | (expr ) | expr expr | let optrec idents = expr in expr | assert expr decl → let optrec idents = expr ; ; | let optrec idents = expr | expr prog → decl prog note that a program (prog ) is a list of expressions mixed with let declarations (let declarations, as opposed to let expressions, don’t have in). the let declarations may optionally be followed with two semicolons. as noted in lecture, these semicolons are used to terminate input in the ocaml toplevel; they’re optional in actual programs... but leaving them out can sometimes confuse the parser... (a) (5 points) as a warmup: even the expression nonterminal introduces ambiguity into this gram- mar. give an example of a string derived from the nonterminal expr that is ambiguous, that is, can be parsed in two or more different ways (has two or more different parse trees). your string must be syntactically valid according to the above grammar, but doesn’t need to be a valid ocaml expression (e.g., can have unbound variables). (b) (4 points) give an example of a string derived from the above grammar (from nontermi- nal prog ) that is ambiguous because of the absence of a double-semicolon at the end of a declaration (that is, your string should have two or more possible parse trees, but adding two semicolons to all of the let declarations in your string should make it only have one parse tree). as above, your string must be syntactically valid according to the above grammar, but doesn’t need to be a valid ocaml program (e.g., can have unbound variables). (c) (4 points) suggest a change to the grammar, other than requiring let declarations to have double semicolons, which would solve this problem. you don’t need to specify the new grammar explicitly. your new grammar doesn’t need to allow exactly the same set of strings, but it should allow roughly the same set of ocaml programs. 0="" n="" n="" n="2a," a="" ≥="" 0="" n="" +="" 1="" −1="" n="2a" +="" 1,="" a="" ≥="" 0="" −1="" n="" +="" 1="" means="" “if="" in="" a="" negative="" state,="" stay="" in="" that="" state="" regardless="" of="" input;="" if="" in="" a="" positive="" even="" state,="" increment="" by="" one="" on="" an="" a="" and="" go="" to="" state="" −1="" on="" a="" b;="" if="" in="" a="" positive="" odd="" state,="" go="" to="" state="" −1="" on="" an="" a="" and="" increment="" by="" one="" on="" a="" b.”="" note="" that="" the="" −1="" entries="" in="" the="" table="" mean="" “go="" to="" the="" state="" −1”="" and="" not="" “go="" to="" state="" n="" −="" 1="" (decrement="" by="" one)”.="" also="" note="" that,="" despite="" its="" compact="" representation,="" the="" transition="" function="" described="" is="" total,="" that="" is,="" it="" has="" exactly="" one="" entry="" for="" each="" symbol="" and="" every="" possible="" value="" of="" n.="" in="" describing="" dias="" in="" this="" question,="" you="" don’t="" need="" to="" use="" exactly="" this="" format="" for="" describing="" transition="" functions,="" but="" make="" sure="" that="" your="" description="" is="" mathematically="" precise="" and="" it’s="" clear="" what="" you="" mean.="" (a)="" (3="" points)="" assume="" that="" the="" above="" transition="" table="" is="" for="" a="" dia="" with="" accepting="" states="" f="{2a" |="" a="" ∈="" z,="" a="" ≥="" 0},="" that="" is,="" the="" positive="" even="" integers.="" give="" a="" regular="" expression="" (using="" only="" the="" standard="" syntax="" elements:="" a,="" b,="" ϵ,="" |,="" ∗="" and="" concatenation)="" that="" accepts="" the="" same="" language="" as="" the="" above="" dia.="" (b)="" (3="" points)="" assume="" that="" the="" above="" transition="" table="" is="" for="" a="" dia="" with="" accepting="" states="" f="{2a" +="" 1="" |="" a="" ∈="" z,="" a="" ≥="" 0},="" that="" is,="" the="" positive="" odd="" integers.="" give="" a="" regular="" expression="" (using="" only="" the="" standard="" syntax="" elements:="" a,="" b,="" ϵ,="" |,="" ∗="" and="" concatenation)="" that="" accepts="" the="" same="" language="" as="" the="" above="" dia.="" (c)="" (6="" points)="" as="" it="" happens,="" dfas="" are="" a="" special="" case="" of="" dias.="" describe="" a="" procedure="" for="" turning="" any="" dfa="" into="" a="" dia="" that="" recognizes="" the="" same="" language.="" for="" simplicity,="" assume="" the="" dfa="" is="" described="" by="" a="" (finite)="" set="" of="" states="" s="" represented="" by="" consecutive="" nonnegative="" integers="" (0="" through="" |s|="" −="" 1),="" and="" the="" start="" state="" s0="" is="" 0.="" include="" how="" to="" construct="" the="" three="" necessary="" features="" of="" the="" dia:="" the="" alphabet,="" the="" set="" of="" accepting="" states,="" and="" the="" transition="" function.="" make="" sure="" your="" transition="" function="" is="" total,="" as="" defined="" above="" (if="" it="" is="" not,="" your="" automaton="" is="" not="" deterministic!)="" on="" the="" other="" hand,="" it="" is="" not="" the="" case="" that="" every="" dia="" can="" be="" turned="" into="" a="" dfa:="" dias="" are="" considerably="" more="" powerful.="" consider="" the="" language="" over="" the="" alphabet="" σ="{a," b},="" consisting="" of="" strings="" with="" the="" same="" number="" of="" as="" and="" bs="" (but="" in="" any="" order).="" examples="" of="" strings="" in="" this="" language="" are="" ϵ,="" ab,="" ba,="" abbbabaa.="" (d)="" (3="" points)="" explain="" in="" a="" short="" paragraph="" why="" this="" language="" is="" not="" regular,="" that="" is,="" why="" it="" cannot="" be="" represented="" by="" a="" regular="" expression="" or="" recognized="" by="" an="" nfa="" or="" dfa.="" you="" do="" not="" need="" to="" give="" a="" formal="" proof.="" (e)="" (4="" points)="" construct="" a="" dia="" that="" accepts="" exactly="" the="" strings="" in="" the="" language="" over="" the="" alpha-="" bet="" σ="{a," b}="" described="" above.="" make="" sure="" to="" specify="" the="" set="" of="" accepting="" states="" and="" a="" total="" transition="" function.="" now="" consider="" the="" language="" over="" the="" alphabet="" σ="{(," )}="" consisting="" of="" only="" strings="" with="" correctly="" matched="" parentheses.="" this="" language="" is="" defined="" by="" the="" following="" grammar:="" p="" →="" ϵ="" |="" p="" p="" |="" (p="" )="" as="" we="" saw="" in="" class,="" it="" is="" not="" possible="" to="" construct="" a="" dfa="" or="" nfa="" to="" recognize="" this="" language.="" (f)="" (6="" points)="" construct="" a="" dia="" that="" accepts="" exactly="" the="" strings="" in="" the="" language="" over="" the="" alpha-="" bet="" σ="{(," )}="" described="" above.="" make="" sure="" to="" specify="" the="" set="" of="" accepting="" states="" and="" a="" total="" transition="" function.="" 2="" right="" recursion="" (12="" points)="" a="" grammar="" is="" right-recursive="" if="" a="" nonterminal="" a="" has="" a="" production="" a="" →="" αb="" such="" that="" b="" ⇒∗="" a.="" a="" special="" case="" is="" immediate="" right="" recusion,="" where="" there="" is="" a="" production="" a="" →="" αa.="" for="" example,="" the="" following="" grammar="" is="" right="" recursive="" because="" of="" the="" immediate="" right="" recursion="" in="" nonterminal="" a.="" s="" →="" a="" a="" →="" cca="" |="" dba="" |="" a="" b="" →="" c="" |="" b="" c="" →="" c="" |="" d="" (a)="" (4="" points)="" explain="" briefly="" why="" d="" ∈="" follow(b).="" (b)="" (4="" points)="" suppose="" that,="" using="" the="" above="" grammar,="" s="" ⇒∗="" s1s2="" .="" .="" .="" sn="" and="" s1,="" .="" .="" .="" ,="" sn="" are="" all="" terminals="" (that="" is,="" s1s2="" .="" .="" .="" sn="" is="" a="" sentence="" of="" s).="" what="" are="" the="" possible="" terminals="" that="" sn="" could="" be="" (that="" is,="" what="" could="" be="" the="" last="" terminal="" in="" a="" sentence="" derived="" from="" s)?="" (c)="" (4="" points)="" we="" know="" that="" left="" recursion="" causes="" problems="" in="" top-down="" parsing.="" since="" bottom-up="" (lr)="" parsing="" is="" basically="" the="" reverse="" of="" top-down="" parsing,="" you="" might="" think="" that="" would="" mean="" we="" can’t="" use="" right-recursive="" grammars="" in="" bottom-up="" parsing.="" in="" fact,="" this="" actually="" isn’t="" a="" problem.="" explain="" why="" in="" a="" short-ish="" paragraph.="" 3="" ;;="" (13="" points)="" consider="" the="" following="" fragment="" of="" a="" grammar="" for="" ocaml:="" optrec="" →="" rec="" |="" ϵ="" ident="" →="" [a="" −="" z][a="" −="" z,="" a="" −="" z,="" 0="" −="" 9,="" ,r="" ]∗="" idents="" →="" ident="" |="" ident="" idents="" expr="" →="" ident="" |="" (expr="" )="" |="" expr="" expr="" |="" let="" optrec="" idents="expr" in="" expr="" |="" assert="" expr="" decl="" →="" let="" optrec="" idents="expr" ;="" ;="" |="" let="" optrec="" idents="expr" |="" expr="" prog="" →="" decl="" prog="" note="" that="" a="" program="" (prog="" )="" is="" a="" list="" of="" expressions="" mixed="" with="" let="" declarations="" (let="" declarations,="" as="" opposed="" to="" let="" expressions,="" don’t="" have="" in).="" the="" let="" declarations="" may="" optionally="" be="" followed="" with="" two="" semicolons.="" as="" noted="" in="" lecture,="" these="" semicolons="" are="" used="" to="" terminate="" input="" in="" the="" ocaml="" toplevel;="" they’re="" optional="" in="" actual="" programs...="" but="" leaving="" them="" out="" can="" sometimes="" confuse="" the="" parser...="" (a)="" (5="" points)="" as="" a="" warmup:="" even="" the="" expression="" nonterminal="" introduces="" ambiguity="" into="" this="" gram-="" mar.="" give="" an="" example="" of="" a="" string="" derived="" from="" the="" nonterminal="" expr="" that="" is="" ambiguous,="" that="" is,="" can="" be="" parsed="" in="" two="" or="" more="" different="" ways="" (has="" two="" or="" more="" different="" parse="" trees).="" your="" string="" must="" be="" syntactically="" valid="" according="" to="" the="" above="" grammar,="" but="" doesn’t="" need="" to="" be="" a="" valid="" ocaml="" expression="" (e.g.,="" can="" have="" unbound="" variables).="" (b)="" (4="" points)="" give="" an="" example="" of="" a="" string="" derived="" from="" the="" above="" grammar="" (from="" nontermi-="" nal="" prog="" )="" that="" is="" ambiguous="" because="" of="" the="" absence="" of="" a="" double-semicolon="" at="" the="" end="" of="" a="" declaration="" (that="" is,="" your="" string="" should="" have="" two="" or="" more="" possible="" parse="" trees,="" but="" adding="" two="" semicolons="" to="" all="" of="" the="" let="" declarations="" in="" your="" string="" should="" make="" it="" only="" have="" one="" parse="" tree).="" as="" above,="" your="" string="" must="" be="" syntactically="" valid="" according="" to="" the="" above="" grammar,="" but="" doesn’t="" need="" to="" be="" a="" valid="" ocaml="" program="" (e.g.,="" can="" have="" unbound="" variables).="" (c)="" (4="" points)="" suggest="" a="" change="" to="" the="" grammar,="" other="" than="" requiring="" let="" declarations="" to="" have="" double="" semicolons,="" which="" would="" solve="" this="" problem.="" you="" don’t="" need="" to="" specify="" the="" new="" grammar="" explicitly.="" your="" new="" grammar="" doesn’t="" need="" to="" allow="" exactly="" the="" same="" set="" of="" strings,="" but="" it="" should="" allow="" roughly="" the="" same="" set="" of="" ocaml="">