B

Alphabet

is a finite set of symbols

Sigma

symbol for alphabet

String

a finite sequence of symbols over some alphabet

Epsilon

represents the empty string

Epsilon

identity element for concatenation

Exponent like notation

we use _ _ _ for self-concatenation

|x|

denotes the length of a string

Formal language

a set of string over some alphabet

Kleen closure of E

set of all possible strings that can be formed using the symbols in E

E*

symbol of Kleene closure of E (sigma)

Regular Expression

is an algebraic-like expression that describes a language

Empty set

is also a regular expression which represents the empty language {} with zero strings in it

o/

symbol for an empty set

Regular language

a language is a _ _ if it can be described by a regular expression

Languages

problem definitions, viewed as abstractions (1)

Automata

flowchart-like solutions, viewed as abstractions (2)

Regular expressions

structured solutions involving sequence, selection, and iteration constructs, viewed as abstractions (3)

Concatenation

regex, sequence

Union

regex, selection

Kleene star

regex, iteration

DFA

unique state for every state q and every symbol a, so the transition table is a complete table

Deterministic Finite Automaton

meaning of DFA

Trap State

converting an incomplete DFA into a complete one by adding a _ _

(Q, E, g, q0, F)

a DFA is completely specified by the structure M equals

Set of state

what does Q mean, equals {q0, q1, …, qn}

Input Alphabet

what does Sigma mean, e.g Σ equals {a, b}

Transition Function

what does δ mean, δ: Q x Σ -> Q

Start State

what does q0 mean

Final State

what does F mean

Current State, Remaining Input

we represent the status of an execution of a DFA with the pair ( _ _)

NFA

a string x is accepted by an _ if there is a path that eventually ends in some final state

Nondeterministic Finite Automata

meaning of NFA

2^Q

in NFA, δ is also a transition function, but the range is not just Q or the set of states, but rather the power set of Q

Set of possible new states

In NFA, (current state, symbol scanned) -> {}