CS 390 Midterm Review

Module 1

Deductive proof

a proof that begins with known facts, assumptions, or definitions, and uses logical reasoning to conclude.

Proof by contradiction

assuming the opposite of what we want to prove. if the assumption leads to a contradiction or an impossible result, then the original statement must be true.

Mathematical induction

a proof technique used to prove statements involving natural numbers or recursive patterns

Two main steps of mathematical induction

Step 1 - Base Case: show that the statement is true for the starting value.

Step 2 - Inductive Step: assume the statement is true for some value. then prove it must also be true for.

Function

a function can be viewed as a mapping between sets

Language

a set of strings

String

a sequence of symbols from an alphabet

Alphabet

any finite set of symbols

Empty string

a string containing no symbols. in theoretical computer science, we usually write it as:

Zero Power

concatenating zero strings gives out an empty string

Kleene Star

A*; all strings that can be formed by concatenating zero or more strings from A

Lexical Processing

breaks a stream of symbols into smaller meaningful units called tokens

Syntax

describes how tokens can be organized to from legal sentences in a language

Semantics

describes the meaning of a sentence or statement