1.1 FINITE AUTOMATA (endanleg stöðuvél)

Question 1

What is finite automata good for ?

Answer 1

They are good models for computers with extremely limited amount of memory

Question 2

What are finite automata and their probabilistic counterpart Markov chains useful for?

Answer 2

Attempting to recognize patterns in data.

Question 3

What is a state diagram ?

Answer 3

It has a start state indicated by an arrow pointing from nowhere, an accept state with a double circle and the arrows going from one state to another are called transitions

Question 4

The output of finite automata ?

Answer 4

accept or reject

Question 5

The formal definition says that a finite automaton is a list of those five objects:

Answer 5

set of states, input alphabet, rules for moving, start state, and accept states.

Question 6

In mathematical language, a list of five elements is often called

Answer 6

a 5-tuple.

Question 7

A finite automaton is a 5-tuple (Q, Σ, δ, q0, F ), where

Answer 7

1. Q is a finite set called the states,
2. Σ is a finite set called the alphabet,
3. δ : Q × Σ−→ Q is the transition function, 4. q0 ∈ Q is the start state, and
4. F ⊆ Q is the set of accept states.

Question 8

If A is the set of all strings that machine M accepts, we say

Answer 8

that A is the language of machine M and write L(M ) = A.

We say that M recognises A or that M accepts A.

Question 9

A machine may accept several strings, but it always recognizes only one language. If the machine accepts no strings, it still recognizes one language

Answer 9

the empty language ∅.

Question 10

A language is called a regular language if some finite automaton recognizes it.

Question 11

We define three operations on languages, called the regular operations, and use them to study properties of the regular languages.

Answer 11

They are union, concatenation, and star

Question 12

Union

Answer 12

A∪B={x|x∈A or x∈B}.

It simply takes all the strings in both A and B and lumps them together into one language.

Question 13

Concatenation

Answer 13

A◦B={xy|x∈A and y∈B}.

It attaches a string from A in front of a string from B in all possible ways to get the strings in the new language.

Question 14

Star

Answer 14

A∗ ={x1x2…xk|k≥0 and each xi ∈A}.

The star operation is a bit different from the other two because it applies to a single language rather than to two different languages. That is, the star oper- ation is a unary operation instead of a binary operation. It works by attaching any number of strings in A together to get a string in the new language. Because “any number” includes 0 as a possibility, the empty string ε is always a member
of A∗, no matter what A is.

Question 15

When we say that N is closed under multiplication, we mean

Answer 15

that for any x and y in N, the product x × y also is in N.

Question 16

N is not closed under division

Answer 16

as 1 and 2 are in N but 1/2 is not.

Question 17

a collection of objects is closed under some operation if applying that operation to members of the collection returns

Answer 17

an object still in the collection.

Question 18

The class of regular languages is closed under the union operation.

Answer 18

meaning : if A1 and A2 are regular languages, so is A1 ∪ A2 ?

Question 19

The class of regular languages is closed under the concatenation operation.

Answer 19

In other words, if A1 and A2 are regular languages then so is A1 ◦ A2.

Question 20

If the start state is also an accept state it accepts the….

Answer 20

the empty string ε. As soon as a machine begins reading the empty string, it is at the end; so if the start state is an accept state, ε is accepted.