Q5 [15 pts]
a) Convert the following NFA to a DFA:
0 1
----------------------
-> a || {a} | {a,b}
b || {c} | {c}
c || {d} | {d}
d || {e} | {e}
* e || {} | {}
b) Informally describe the language that it accepts.
Convert the following NFA given by M to a DFA. Show your work
which includes both state diagrams.
M = ( {q0, q1, q2} , {a, b} , δ, q0, {q1}) with the state table
given
a
b
q0
{q1, q1}
q1
null
{q2}
q2
null
{q2}
For the following lexical
specification:
Give NFA and DFA
Using your DFA, Implement a lexical analyzer using the state
table approach shown in class
• keywords:
if wh pr
• Identifiers. An
identifier is a sequence of one or more letters
• Integer literals.
An integer literal is a sequence of one or more decimal digits.
• Any of the following one- or
two-character symbols:
= ( ) { }
/ * - +
< <= ==
!=
• Note...
Consider the language defined as such:
L = { w$w’ : w is a string of
numbers 0-9 and can be of length ≥ 0, and w’ is the reverse string
of w}
Write a recursive grammar that defines
all strings in the language.
Using the language above, write the Java code (using recursion)
that will recognize if a string is part of the language or
not.