1 - Regular languages

Question 1

full arden proof

Answer 1

L = ULuV L = U*V

L ⊇ UV Induction
L ⊆ UV Contradiction

Question 2

NFA DFA equivalence?

Answer 2

powerset construction

For each possible state, we add a powerset transition and stuff

Question 3

reg to NFA?

Answer 3

For each operation we have an automata

concatenation, choice and klenee star

Question 4

NFA to reg?

Answer 4

System of equations
1 Variable for each state
solve system using arden’s lemma