Math代写|算法代写 :这是一个涉及NFA的代写作业
From each category, choose ONE question to answer:
Category 1.
Build an NFA over {0,1} that is able to recognize the following languages:
If you choose question 1, then you have to choose question 2 for Category 4.
(1)
___ L is the set of strings that contains NO consecutive same symbols, like “00” or
“11”
(2)
___ L is the set of strings that are even length AND contains ’01’ AND ’10’.
Category 2.
Provide regular expressions for the following language over the alphabet {a,b}:
(1)
___ L is the set of strings that contains NO consecutive same symbols, like “aa” or
“bb”
(2)
___ L is the set of all strings where each b in the string is followed by exactly one
or three a’s , like “ba”, “baaaa”
Category 3.
Construct a pushdown automaton for the following language.
If you choose question 1, then you have to choose question 2 for Category 4.
(1)
____ L = {ai
bj | j = 2i +1, i>=0 }
(2)
____ L = {ai
bj
ck | i, j >=0, k = i +j}
Category 4.
Construct a context-free grammar for the following language.
(1)
____ L = {ai
bj | j = 2i +1, i>=0 }
(2)
____ L = {WcW*}, W = {a|b}, i.e.: acbbb, aca