CMSC 141: Automata and Language Theory

Proof

A sequence/series of formal statements containing givens and deductions.

Set

A collection (unordered) of objects; the objects are called its elements or members.

PowerSet

The set of all subsets of a set S, denoted by P(S).

Partition

A subset of 2^A such that each element of A is in one and only one set of the partition.

Relation

A connection between the elements of two or more sets.

Binary Relation

A subset of A × B, where A and B are two sets.

Function

An association of each object of one kind with a unique object of another kind.

One-to-One

If for any two distinct elements a, a’, f(a) != f(a’).

Onto

If each element of B is the image under f of some element of A.

Bijection

If a function is both one-to-one and onto.

Direct Proof

A sequence of statements which are either givens or deductions from previous statements.

Proof by CounterExample

Proving/disproving by giving one example that disproves the case.

Proof by Contradiction

Assuming the opposite proposition is true and showing a contradiction.

Proof by Mathematical Induction

Contains a Base Step, Inductive Hypothesis, and Inductive Step.

Set Equality Proving

To prove that two sets are equal, one must prove that both sets are subsets of each other.

Symbol

An atomic unit such as a digit, character, or letter.

Alphabet (Σ)

A finite set of symbols denoted by Σ.

String

A finite length sequence of symbols, which may be empty (denoted by ε).

Concatenation

The string formed by string x followed by string y.

Substring

A string v is a substring of a string w if w can be expressed as xyv for some strings x and y.

Suffix

A substring v of some string w where w can be expressed as xv.

Prefix

A substring v of some string w where w can be expressed as vy.

Kleene Star (L*)

The set of all strings obtained by concatenating zero or more strings from L.

Kleene Plus (L+)

The language LL* - Kleene star without the empty string.

Regular Expression

A language described by means of symbols and operations such as ∪ and *.

Language Recognition Device

An algorithm designed to answer whether a string w is a member of language L.