Regular Languages Flashcards

(33 cards)

1
Q

What is a Finite State Machine (FSM)?

A

A model that shows how a machine or system can change from one state to another based on an external input

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What are the 2 ways a FSM can be represented?

A
  • State Transition Diagram
  • State Transition Table
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

What are the essential components of a FSM?

A
  • A finite set of input symbols (its alphabet)
  • A finite set of states that the machine can be in
  • An initial state - S0
  • A state-transition function which determines which state to transition to based on the current state and input
  • One or more accepting states
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

In how many states can a FSM be in at once?

A

1

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

What is a dead state?

A

When it enters a state where it is no longer possible for it to reach an accepting state therefore the input must be invalid.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What are some systems that FSM might be used to model?

A
  • Digital (hardware) systems
  • Software compilers
  • Syntax parsing
  • Network protocols
  • Games
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What is the “language” of a FSM?

A

The set of all possible input strings that follow a path from the initial state to an accepting state.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

What does it mean for a finite state machine to be deterministic?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

What is a Finite State Automata?

A

A FSM that doesn’t produce an output that always has an initial state and at least one accepting state

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

What is a Mealy Machine?

A

A FSM that produces an output as its inputs are being processed rather than once an accepting state has been reached

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

What are some differences of the Mealy Machines when compared to automata?

A
  • Produce an output while the inputs are being processed
  • They do not have accepting states
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

What are the uses of Mealy Machines?

A
  • Encrypting a message into cipher text
  • Controlling traffic lights
  • Vending machine payment collection and display of amount remaining
  • Digital logic circuits
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

What is a set?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

What is the Cartesian Product of two sets?

A

The Cartesian product of two sets, A and B, is written as A x B and is the set of all ordered pairs (a,b) where a ∈ A and b ∈ B

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

What is a subset?

A

A subset of S is a set whose values are all members of S. Written as A ⊆ B

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

What is a proper subset?

A

A proper subset of S is a set where every value is a member of S but it does not contain all members of S. Written as A ⊂ B.

17
Q

What is the cardinality of a finite set?

A

The number of items in the finite set

18
Q

What are the different set operations?

A
  • 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)
19
Q

What is the union of two sets?

A

The union of two sets , A and B, will contain all unique values in A and B.

20
Q

What is the intersection of two sets?

A

The intersection of two sets, A and B, will contain all values that are present in both A and B.

21
Q

What is the difference of two sets?

A

The difference of two sets, A and B, will contain all the elements that are in set A but are NOT in set B.

22
Q

What is a finite set?

A

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.

23
Q

How to show a compact representation of a string with equal numbers of 1s and 0s?

A

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

24
Q

What is an infinite set?

A

A set with an infinite number of items.

25
What is the difference between a countably infinite set and a non-countable infinite set?
A countably infinite set is an infinite set that can be counted off by the natural numbers. R is non-countable infinite set.
26
What is the initial state symbol in state transition diagrams?
27
What is the accepting state symbol in state transition diagrams?
28
What is the transition symbol in state transition diagrams?
29
What is transition symbol **with output** in state transition diagrams?
30
What is a regular expression?
31
What are the metacharacters in regular expressions?
32
What are the uses of regular expressions?
33
What is a regular language?