Regular Languages

Question 1

What is a mealy machine?

Answer 1

A finite state machine that generates an output for every transition.

Question 2

What does l mean in regular expressions?

Answer 2

Or, it separates alternatives.

Question 3

What does * mean in regular expressions?

Answer 3

0 or more of the preceding element.

Question 4

What does + mean in regular expressions?

Answer 4

1 or more of the preceding element.

Question 5

What does ? mean in regular expressions?

Answer 5

0 or 1

Question 6

Define an intractable problem.

Answer 6

A problem that can be solved but not in polynomial / reasonable time.

Question 7

How can you solve some intractable problems?

Answer 7

Using heuristic methods.

Question 8

Define a set.

Answer 8

An unordered collection of elements.

Question 9

∈

Answer 9

Member of

Question 10

∉

Answer 10

Not a member of

Question 11

∩

Answer 11

Intersection

Question 12

∪

Answer 12

Union

Question 13

A\B

Answer 13

Elements that are in A but not B (difference)

Question 14

|

Answer 14

Such that

Question 15

Λ

Answer 15

And

Question 16

Define a Turing Machine

Answer 16

A computer with a single fixed program. (it only solves one problem)

Question 17

What are the components of a Turing Machine?

Answer 17

• A finite set of states
• A finite alphabet of symbols
• An infinite tape with marked off squares
• A sensing read-write head that travels along the tape one square at a time.

Question 18

Line for a one-to-one relationship

Answer 18

─

Question 19

Line for a one-to-many relationship

Answer 19

─

Question 20

Line for a many-to-many relationship

Answer 20

> ─