4.4.2 Regular Languages 4.4.3 Context-free languages

Question 1

What is a Finite State Machine?

Answer 1

A Finite State Machine does not have output it is an abstract representation used in designing computer systems and logic circuits

Question 2

What is a State Transition Diagram?

Answer 2

Uses circles to represent the states that a system may be in and arrows to represent the transitions between states

1) Start state
2) Accept State

Question 3

What is a mealy machine?

Answer 3

A mealy machine is a type of FSM with an output that are determined by both its current state and the current input

Question 4

What is a State transition table?

Answer 4

A State transition table is an alternative way of representing an FSM in a tabular form

Question 5

What is a Set?

Answer 5

1) A set is an unordered collection of values or symbols in which each value or symbol occurs at most once

Question 6

How do you represent a set?

Answer 6

A = {1, 2, 3, 4, 5}

Question 7

How do you represent an empty set?

Answer 7

1) {} (Curly Braces)

2) Ø

Question 8

Use Set comprehension to define this set

A = {x | x ∈ ℕ ∧ x ≥ 1 }

Answer 8

1) A is equal to x such that x is a member of the natural numbers and x is bigger than or equal to 1

Question 9

What is a finite set?

Answer 9

A set whose elements can be counted off by natural numbers up to a particular number

E.g. 10 is the 6th number in set a
A = {1,2,4,6,8,10}

Question 10

What is the cardinality of a finite set?

Answer 10

The number of elements in the set

Question 11

What is a countably infinite set?

Answer 11

A set that can be counted off by the natural numbers

Question 12

What is a Cartesian product of sets?

Answer 12

1) Written as X and Y and X cross Y is the set of all ordered pairs (a,b) where a is a member of A and b is a member of B

2) E.g. A = {1,3,5} B = {12,25,40}
C = {(1,12), (1,25), (1,40), (3,12), (3,25), (3,40) , (5,12), (5,25), (5,40)

Question 13

What is an infinite set?

Answer 13

1) Can be countable or uncountable and is not finite

Question 14

What is a subset?

Answer 14

1) A subset is where every member of one set is also a member of another set
2) A ⊆ B = Every member of set A is also a member of set B

Question 15

What is a proper subset?

Answer 15

A proper subset is when a set is a subset of another set but is not equal to another set

Question 16

What is a countable set?

Answer 16

A countable set is a set with the same cardinality (number of elements) as some subsets of natural numbers

Question 17

What is membership?

Answer 17

The property of an element being within a set

Question 18

What is Union?

Answer 18

A∪B is the set of things that belong to either A,A or B,b

Question 19

What is Intersection?

Answer 19

A∩B The set of things that belong to both A,A and B,B

Question 20

What is difference?

Answer 20

List of elements that are in set A but not in Set B denoted by

• A - B
• A / B

Question 21

What is a Regular Expression?

Answer 21

1) A way of describing a set
2) Allows types of languages to be described in a convenient shorthand notation
3) E.g. a(aIb) * = {a, aa, ab, aaa, aab, aba, ….}

Question 22

What is the relationship between the regular expressions and the FSM’s?

Answer 22

They are equivalent ways of defining a regular language

Question 23

What does this metacharacter indicate?

ab*

Answer 23

1) Indicates that there are zero or more of the preceding element
2) In this case zero or more b’s
3) ab, ab , abb, abbb

Question 24

What does this metacharacter indicate?

a+b

Answer 24

1) Indicates that there are one or more of the preceding element
2) ab, aab, aaab

Question 25

What does this metacharacter indicate?

Dialog(ue)?

Answer 25

1) Indicates zero or one of the preceding element

2) Dialog, Dialogue

Question 26

What does this metacharacter indicate?

DId)is(cIk

Answer 26

1) Indicates scope and precedence of the operators

2 ‘Disc’, ‘disc’, ‘Disk’ and ‘disk’

Question 27

What does this metacharacter indicate?

Edward)I(Eddie)I(Ed

Answer 27

1) Boolean OR a vertical bar separates alternatives

2) Edward, Eddie, Ed

Question 28

What can a language be called if it can represent a regular expression?

Answer 28

A regular language

Question 29

What is a regular language?

Answer 29

Any language that a FSM can accept

Question 30

What is the structure of Backus- Naur form (BNF)

Answer 30

1) LHS ::= RHS
2) ::== ‘is defined by’
3)
4) E.g. ::= 0I1I2I3I4I5I6I7I8I9

Question 31

What is Parsing?

Answer 31

1) Determining whether a given statement is valid given the BNF definition