Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due
CS 162--Formal Languages and Automata Theory
1. (50 points). Regular languages.
(a) Give a regular expression for the set of all strings of a’s and b’s that have at least 2 a’s.
(b) What is the Pumping lemma for regular languages, including its three conditions?
2. (50 points). DFAs.
(a) Give a formal definition of a deterministic finite automaton (DFA), including a description of its transition function, δ.
(b) Draw a DFA for the language, L = {a
na
n
| n ≥ 1}.
3. (50 points). Draw an NFA for the language, L = {(10)
n1
m | n ≥ 1 is odd and m ≥ 0 is even}.
Note: the parentheses, “(” and “),” in this definition are just for grouping purposes—these are not symbols in the alphabet for this language.
4. (50 points). Give the NFA resulting from the algorithm for converting the regular expression, 01+10∗
, to an NFA for the same language.
5. (50 points). Context-free Grammars. Give a context-free grammar for the language,
L = {0
n1
n2
m3
m | n ≥ 1 and m ≥ 1}.
6. (50 points). Pushdown Automata. Give a proof of the statement, “If L is a regular language, then there is a pushdown automata, A, such that L = L(A), that is, L is the language accepted by A.” You may assume the existence of an NFA, B, for L, that is, such that L = L(B), in which case you need to explain how to construct A from B, including how to define the transition function for A from the transition function for B.