Week 1

Question 1

The alphabet?

Answer 1

(Σ) which is a set of characters such as {a,b,c}

Question 2

Σ*

Answer 2

the set of all words

Question 3

Language

Answer 3

is a set of words which is subset of Σ*

Question 4

The regexp a matches only the word?

Answer 4

a

Question 5

The regexp ε matches only ?

Answer 5

The empty word ε

Question 6

The regexp 0 matches ?

Answer 6

none

Question 7

the regexp EF matches?

Answer 7

(a word matches by E) + (a word matches by F)

Question 8

the regexp E|F matches?

Answer 8

(a word match by E) or (a word matches by F)

Question 9

the regexp E* matches?

Answer 9

0 or more

Question 10

The precedence rule of regexp?

Answer 10

1- * + ?
2- juxtaposition
3- |

Question 11

the regexp E+ ?

Answer 11

EE* , one or more

Question 12

E?

Answer 12

ε | E, zero or one

Question 13

Regular language?

Answer 13

Language that can be represented by a regular expression

Question 14

decision problem?

Answer 14

is a problem that, for any given argument, has a Yes/No answer

Question 15

Decidable decision problem?

Answer 15

when there is some program that, given an argument, says whether the answer is Yes or NO

Question 16

Deterministic finite automata consists of:

Answer 16

· A finite set X of states
· An initial state p ∈ X
· A trainstion function δ: X ×Σ →X
A set of acceptiong states: Acc ⊆X

Question 17

Ismorphism?

Answer 17

A bijiction that perserves the intial state, the accepting state and the transtion function.

Question 18

particial DFA?

Answer 18

· δ is merely a partical function, sometime it can be undefined
· As soon as a character cannot be an input, the word is rejected
A partical DFA can also have no initial state but then every word is rejected

Question 19

convert PDFA to DFA?

Answer 19

We just add extra non-acception state, error state. Transitions that are undefined in particial DFA go to the error state and every transition from the error state goes to the error state.

Question 20

nonderministic finite automata?

Answer 20

· δ is a relation not a function (since one state maps to two different states with the same character)
. it can have more than 1 initial states

A word w is acceptable when there exists a path from an initial state to an accepting state that goes through the characters of w.

Question 21

Determinisation?

Answer 21

the process of of converting NFA to DFA.

Question 22

NFA with ε-transiotns?

Answer 22

· ε-Transitons: it moves from one state to another without inputing any character.
A word w is acceptable when there exists some path from initial state to an accepting state that goes through the characters of w padding with ε-transtions.

Question 23

Slow b-transtions?

Answer 23

consists of zero or more ε-transitions ending with b-transtion.

Question 24

Slow accepting:

Answer 24

consists of zero or more ε-transitions ending with accepting state.