Deterministic Finite Automata notation

A = {Q, Σ, δ, q_0, F}
Q - set of states

Σ - alphabet

δ - transition function

q_0 - start state

F - finale state

δ(current state, character) = state you would have transitioned to

δ(current state, character) = state you would have transitioned to

How do you reverse a language represented as a DFA

- Change start state to final state

- Change finale state(s) to start state(s)

- Reverse the transitions

(optional) - create a new state that λ transitions to all the start states

How to tell if something is a Regular Language?

A DFA or NFA can recognize it

Difference between DFA and NFA

DFA due to its deterministic nature must have a transition out of every state for every character in the alphabet, and NO λ transitions. Also note every DFA is technically also an NFA

NFA doesn't have to have a transition for every alphabet character and can have λ transitions. Also note every NFA has an equivalent DFA

some primitive notation

Φ = {}

λ = {λ}

a means where 'a' is in Σ denotes {a}

Closure properties for R and S

R · S

R + S

R*

convert this to a reg ex using (R_ij)^k method

in 1-16 notes

convert this to a reg ex using state ripping

in 1-16 notes

convert this to a reg ex using Arden's

in 1-21 notes

Show the relation between the following family of languages. Regular, Deterministic Context-Free, Context-
Free, and Context-Sensitive

Show the relation between models of computation

True or False: Every NFA does not have an equivalent DFA

true, you can turn an nfa into usually a nasty much larger dfa with stuff like trap states.

Does an algorithm exist for determining if a grammar is considered ambiguous?

no, ambiguity is undecidable

Whenever a new problem is created, what is it considered inherently?

solvable and unsolved

solved is temporal or inherited

temporal

unsolvable/undecidable is temporal or inherited

temporal

unsolved is temporal or inherited

inherited

if we solve that new problem it moves from

solvable and unsolved

to?

solvable and solved

if we find that new problem is unsolvable it moves from

solvable and unsolved

to?

unsolved and solved

Can the CYK parsing algorithm take any type of grammar as input?

CYK operates only on context-free grammars given in Chomsky normal form

Find the minimal equivalent DFA using the method that was shown in class.

1-23 slides

True or False: The reversal operation is closed under regular languages.

true earlier card says how

Express the following FSA as a regular expression using Arden's Theorem..

1-21 slides