Automata and Language Theory

Power set of {1, 2}

{ }, {1}, {2}, {1, 2}

Is the empty set a subset of every set

Yes, and every set is also a subset of itself

Is {a} an element of {a, b}

No, the elements are a and b, but {a} is a subset of {a, b}

Asymmetric versus antisymmetric

Asymmetric means antisymmetric and also no loops (a, a) allowed

Is antisymmetric the opposite of symmetric

No, a relation can be both, such as the identity relation

Complete DFA

A DFA with a transition defined for every state and symbol pair

Language of a DFA, L(M)

The set of all strings that the DFA accepts

Why are NFAs often preferred for design

They are usually smaller and easier to write, while DFAs are easier to run

Conversion chain from regex to DFA

Regular expression to epsilon NFA to NFA to DFA

Epsilon closure with a chain

If q0 goes to q1 and q1 goes to q2 by epsilon, then ECLOSE(q0) = {q0, q1, q2}

0*1?

Any number of 0s, optionally followed by a single 1

1(0101)

Binary strings with an even number of 0s

r + ∅

Equals r

ε*

Equals ε

Is concatenation commutative

No, ab is not the same as ba

Mealy to Moore start state

Use the copy of the original start state with output 0, because Moore prints an extra leading symbol

Mealy bit flipper on input 1011

Output is 0100

Moore output for 3 inputs

4 output symbols, because the start state prints first