CMSCI 485: Theory of Computation

Set

a collection of non-repeatable elements, without any structure other than membership.

∪ (Union of sets)

a set that contains all the values in both sets.

∩ (Intersection of sets)

a set that contains all the elements that are common to both sets

— (Difference of sets)

a set containing all the elements that are in one set but not the other

Complement (S’)

a set that contains all possible elements not in S

Cartesian Product (X)

a collection of ordered pairs produced by both sets

Proper Subset (S₁ ⊂ S)

where there exist an element in S that is not in S₁

Disjoint

where both sets have no common element

Powerset (2^s)

The set of all subsets of a set S, including empty

Alphabet (∑)

a finite set of “symbols”

String

finite sequence of elements from the alphabet

Languages

set of strings from the alphabet

L*

0 or more copies from L concatenated together

L+

1 or more copies from L concatenated together

Automaton

Procceses input string and changes states according to a set of configured rules

Deterministic Finite Automata

A finite state machine where each state has exactly one transition for every input symbol.

Non-deterministic Finite Automata

A finite state machine where each state has more than one possible transition from one state on the same input symbol.

Regular Language

A language that is recognized by a finite automaton (D/N) (L=L(M)), Regex, and (Right/Left) Grammar, and Operations

Grammar Rules

Variables, Terminals, Start Symbols, Production Rules

Defining DFA

M = {Q, Σ, δ, qo, F}

Q

number of finite states

Σ

Alphabet

δ

Transition Function

qo

Start State

F

Final State

Right-Linear Grammar

Where the non-terminals are right of the string of terminals

Left-Linear Grammar

Where the non-terminals are left of the string of terminals

Closure

an operation on elements in a set that gives you another element in the set

Homomorphism

function that takes a letter and transforms it into another letter

Ways to show a Language is Regular

1. DFA

2. NFA

3. Regex

4. Right/Left-Linear Grammar

5. Operations (Concatenate, Union, etc)

Context-Free Grammar

is a formal system used to describe all strings in a language using a set of rules that follows:

S → aS|λ

Ambiguous Grammar

if there exists a string w such that w has two or more distinct parse trees or derivations

Parsing

the process of deriving a string from a grammar

Brute-force Parsing

Trying and seeing all combinations of concatenated grammar, which might get stuck in a loop.

S-Grammar (Simple Grammar)

Where the non-terminals gives us one choice on what to choose