Regular Languages

What is an algorithm

A sequence of steps to complete a task

What is a set?

An abstract data type which stores unordered unique values

what is a finite set?

A set which contains a finite number of items

What is a subset?

A set that contains only values from another set

What is a proper subset?

A subset that is not equal to its parent set.

Define cardinality

The amount of items in a set

What is a countably infinite set?

A set with infinite items that can be counted off using the natural numbers

What is a non - countably infinite set?

A set with infinite items that cannot be counted off using the natural numbers

What does * mean in Regex?

0 or more repetitions

What does + mean in Regex?

1 or more repetitions

What does | mean in regex?

Or

What does ? mean in Regex?

The previous character is optional

What is a context free language?

A set of strings or symbols that follow the rules of context free grammar

What is a non terminal?

Something that can be broken down to more terminals, non terminals or both

What is a terminal?

Something that cant be broken down further

Write address is a number and street it backus-Naur form.

<address> ::= <number><street>

What is Backus - Naur form?

A way of notating context free languages

What is a universal Turing machine?

A Turing machine that is capable of representing any other Turing machine