regular language

Question 1

What is a Finite State Machine?

Answer 1

A computational model that can be in one of a finite number of states at any given time. FSMs can have an output (Mealy machines) or no output.

Question 2

What are the key components of a Finite State Machine?

Answer 2

States (represented as circles), Transitions (represented as arrows), Start state (indicated by an arrow pointing to it), Accept/stop states (represented by double circles), Inputs (labels on arrows), Outputs (if applicable, separated from inputs with a |)

Question 3

What is a valid stop state in an FSM?

Answer 3

A state represented by a double circle that indicates acceptance of the input string.

Question 4

What does the Mealy machine refer to in FSMs?

Answer 4

A type of FSM with output where the output values are determined by the current state and the current input.

Question 5

How can you represent an FSM in diagram form?

Answer 5

Using state transition diagrams where states are circles, transitions are arrows, inputs label the arrows, and double circles represent accept states.

Question 6

How can you represent an FSM in tabular form?

Answer 6

Using state transition tables that show the current state, input, next state, and output (if applicable).

Question 7

What is a set?

Answer 7

An unordered collection of values in which each value occurs at most once.

Question 8

What is set comprehension notation?

Answer 8

A notation that defines a set by stating the properties that its members must satisfy, e.g., A = {x | x ∈ ℕ ∧ x ≥ 1}

Question 9

What does the empty set represent and what are its symbols?

Answer 9

The empty set is the set with no elements. It is represented by {} or Ø.

Question 10

What is the difference between finite and infinite sets?

Answer 10

Finite sets contain a countable number of elements up to a particular number, while infinite sets contain an unlimited number of elements.

Question 11

What is a countably infinite set?

Answer 11

A set that can be counted off by the natural numbers. Examples include the set of integers and the set of natural numbers.

Question 12

What is the cardinality of a finite set?

Answer 12

The number of elements in the set.

Question 13

What is the Cartesian product of sets?

Answer 13

The Cartesian product of two sets X and Y, written X × Y, is the set of all ordered pairs (a, b) where a is a member of X and b is a member of Y.

Question 14

What is a subset?

Answer 14

Set A is a subset of Set B (written A ⊆ B) if all elements of A are also elements of B.

Question 15

What is a proper subset?

Answer 15

Set A is a proper subset of set B (written A ⊂ B) if A is a subset of B, but A ≠ B (i.e., B contains at least one element not in A).

Question 16

What is a countable set?

Answer 16

A set with the same cardinality (number of elements) as some subset of natural numbers.

Question 17

What is set membership?

Answer 17

The relationship between an element and a set that contains it. If x is an element of set A, we write x ∈ A. If not, we write x ∉ A.

Question 18

What is the union of sets?

Answer 18

The union of sets A and B (written A ∪ B) is the set containing all elements that are in A or B or both.

Question 19

What is the intersection of sets?

Answer 19

The intersection of sets A and B (written A ∩ B) is the set containing only the elements that are in both A and B.

Question 20

What is the difference of sets?

Answer 20

The difference of sets A and B (written A \ B or A - B) is defined as the set containing elements that are in A but not in B: A \ B = {x : x ∈ A and x ∉ B}.

Question 21

What is a regular expression?

Answer 21

A way of describing a set using shorthand notation. Regular expressions allow particular types of languages to be described.

Question 22

What does the * metacharacter represent in regular expressions?

Answer 22

0 or more repetitions of the preceding element.

Question 23

What does the + metacharacter represent in regular expressions?

Answer 23

1 or more repetitions of the preceding element.

Question 24

What does the ? metacharacter represent in regular expressions?

Answer 24

0 or 1 repetition of the preceding element (i.e., the element is optional).

Question 25

What does the | metacharacter represent in regular expressions?

Answer 25

Alternation or 'or' - it matches either the expression before or after the symbol.

Question 26

What do parentheses () do in regular expressions?

Answer 26

They group regular expressions together, allowing operations to be applied to the entire group.

Question 27

What is an example of a regular expression and what set does it describe?

Answer 27

a(a|b)* describes the set of strings {a, aa, ab, aaa, aab, aba, ...} - strings starting with 'a' followed by any number of 'a's or 'b's.

Question 28

What is a regular language?

Answer 28

A language is called regular if it can be represented by a regular expression. Equivalently, a regular language is any language that can be accepted by a Finite State Machine.

Question 29

What is the relationship between regular expressions and FSMs?

Answer 29

Regular expressions and FSMs are equivalent ways of defining a regular language. Every regular expression can be converted to an FSM and vice versa.

Question 30

What does the compact representation {0ⁿ1ⁿ | n ≥ 1} mean?

Answer 30

It represents the set of strings with an equal number of 0s followed by 1s, e.g., {01, 0011, 000111, ...}

Question 31

How do you convert a given FSM to a regular expression?

Answer 31

1. Identify the start state and accept states 2. Trace all possible paths from start to accept states 3. For each path, write down the sequence of inputs 4. Combine these sequences using regular expression operators

Question 32

How do you convert a regular expression to an FSM?

Answer 32

1. Break down the regular expression into its components 2. Create states for each component 3. Add transitions between states according to the operations in the expression 4. Mark the final state(s) as accept states

Question 33

What is the difference between a countably infinite set and a non-countable set?

Answer 33

A countably infinite set can be put in one-to-one correspondence with the natural numbers. Non-countable sets (like the real numbers) contain a larger infinity and cannot be paired with natural numbers.

Question 34

What does x ∈ ℕ mean?

Answer 34

x is a member of the set ℕ consisting of the natural numbers {0, 1, 2, 3, 4, ...}