Deterministic Finite Automata

Question 1

What does ∪ mean?

Answer 1

Union

Question 2

What does ∩ mean?

Answer 2

Intersection

Question 3

What does ∈ mean?

Answer 3

Is an element of

Question 4

What does ∉ mean?

Answer 4

Is not an element of

Question 5

The set of all words in an alphabet Σ is denoted by?

Answer 5

Σ∗

Question 6

What defines a language in Σ?

Answer 6

Any subset L⊂Σ∗

Question 7

What is cardinality?

Answer 7

The number of elements in a set.

Question 8

Let w1,w2 ∈Σ∗. We say that w1 is a subword of w2 if?

Answer 8

There
exist words u,v∈Σ∗such that w2 = uw1v.

Question 9

A Finite Automaton (FA) is a collection of five objects
(Q, Σ, δ, s, F) which are?

Answer 9

*Q is a finite set of states;
*Σ is the input alphabet;
*δ: Q×Σ →Q is the transition function;
*s∈Q is the initial state;
*F ⊂Q is the set of accepting states.

Question 10

Define the pumping lemma for regular languages.

Answer 10

Let L be a regular language. There exists an
integer number n > 0 such that any word w ∈L with |w|> n can be represented as
w = xyz where
*y ̸= e
* |xy|≤n,
*xyiz ∈L for all integer i ≥0.

Question 11

What does ⊆ mean?

Answer 11

Is a subset of.

Question 12

What are context free languages closed under?

Answer 12

Union, concatenation, kleene star.

Question 13

Define the pumping lemma for context free grammars.

Answer 13

Let L be a context-free language. Then there
exists an integer number n > 0 such that any word w ∈L with |w|≥n can be
represented as w = uvxyz where
*either v or y is different from e (in other words, |vy|> 0),
* |vxy|≤n,
*for every i ≥0 the word uvixyiz ∈L

Question 14

State the Church Turing thesis.

Answer 14

if a function is effectively calculable it can be implemented on a TM

Question 15

A pushdown automaton is a system
A= (Q, Σ, Γ, s, ∆, F) where?

Answer 15

*Q is a finite set of states,
*Σ is an input alphabet,
*Γ is a stack alphabet,
*s∈Q is an initial state,
*∆ is a transition relation:
∆ ⊂(Q×(Σ ∪{e}) ×Γ∗) ×(Q×Γ∗),
*F ⊂Q is a set of final states.

Question 16

Turing machine (TM) is a system (Q, Σ, Σ0, s, δ, H) where?

Answer 16

*Q is set of states;
*Σ is an alphabet containing ⊔(blank), ◃ (left end symbol), and not con-
taining →and ←;
*Σ0 ⊂Σ {⊔,◃}is the input alphabet;
*s is the initial state;
*H ⊂Q is the set of halting states;
*δ is the transition function,
δ: (Q\H) ×Σ → Q×(Σ ∪{←,→})
such that
(a) for all q∈Q\H if δ(q,◃) = (p,b) then b=→;
(b) for all q∈Q\H and a∈Σ if δ(q,a) = (p,b) then b̸= ◃.