Theory of Computation Flashcards

Question

What is the initial state symbol in state transition diagrams?

Answer 1

Current state, input, output, next state

Answer 2

- digital (hardware) systems - software compilers - syntax parsing - network protocols

Answer 3

The next state is only dependent on the current state and input and hence **requires no memory**.

Answer 4

Finite State Automata

Answer 5

The empty set

Answer 6

An **unordered** collection of values where each value **occurs at most once**.

Answer 7

*S = { e | p }* where e is the **expression** and p is the **predicates**

Answer 8

- ∧ is AND - upside down ∧ for OR

Answer 9

{ 0ⁿ1ⁿ | n >= 1} where n must be a **countable** number

Answer 10

A set whose elements can be counted off by **natural numbers** (at which point the set stops). The number of items in the set is referred to as its cardinality.

Answer 11

A set with an infinite number of items.

Answer 12

A countably infinite set is an infinite set where the items can be counted off by the natural numbers. R is non-countable infinite set.

Answer 13

A x B is the set of all ordered pairs (a,b) where a is an element of A and b is an element of B.

Answer 14

A subset (X) of the set S is a set whose values are all members of S. denoted as X ⊆ S

Answer 15

A subset that does not contain **all** of the elements of the original set. denoted as X ⊂ S

Answer 16

- Union - ∪ - all elements in either set or both - Intersection - ∩ - elements shared by both sets - Difference - / - A/B is all the elements in A but not in B (also written as A-B)

Answer 17

If a problem can be solved in polynomial time, it is described as **tractable**.

Answer 18

It will remain the same tractability as tractability is not dependent on the size of the dataset. // Sorting algorithms are always tractable.

Answer 19

A heuristic approach employs a method of finding a solution that might not be the best. (reducing problem space or changing constraints)

Answer 20

A way of describing the set of strings that conform to a particular pattern in a simple way.

Answer 21

| - or **takes everything on both sides unless contained by brackets** ? - 0 or 1 occurence of the preceding element * - 0 or more repetitions of the preceding element + - 1 or more repetitions of the preceding element () - used to group regular expressions

Answer 22

- Expressing regular languages including those of FSMs - Validating user input

Answer 23

A regular language is one that can be represented by a regular expression.

Answer 24

A language (set of strings) that are defined by context-free grammars, which are made up of production rules.

Answer 25

All regular languages are context-free but not all context-free languages can be represented as a regular expression.

Answer 26

- Terminal symbols - characters in a string that **cannot be broken down further** - Non-terminal symbols - defined in other production rules - Production rules - the rules for replacing the non-terminal symbols

Answer 27

It is a **meta-language** used in order to define **context-free grammars**. Symbols: - - non-termincal symbols - n - a terminal symbol - :: = ab - a production rule, in this case is an a followed by a b

Answer 28

A way of expressing context-free grammars using BNF rules.

Answer 29

- nested brackets cannot be represented in regular expressions - can represent irregular languages

Answer 30

If recursion occurs **between other symbols** it is irregular

Answer 31

- The time they take to complete - The space (memory) that is required to process the algorithm - For a given size of dataset

Answer 32

The mapping of a domain of values to a co-domain.

Answer 33

- O(n!) - factorial time complexity, increase at a greater rate than exponential functions - Considered to be intractable

Answer 34

The step with the worst time complexity determines the overall Big O.

Answer 35

Problems where there is **no certain outcome** or because **limits of hardware** make solving the problem with a certain outcome impractical

Answer 36

Time is independent of input

Answer 37

Halves the number of items each iteration

Answer 38

In a worst case scenario, go through each item once

Answer 39

Nested loop

Answer 40

- An algorithm cannot be written that can determine whether another algorithm will finish with a given input - The halting problem demonstrates that there are some problems that are non-computable

Answer 41

The set of all possible real-world quantities; Includes all rational and irrational numbers; A value that represents any quantity along an infinite number line;

Theory of Computation Flashcards

(74 cards)