Unit 8 - Languages and Automata

Question 1

An alphabet is

Answer 1

a finite and non-empty
set of symbols

Question 2

an alphabet is often denoted with

Answer 2

Σ (Greek letter Sigma)

Question 3

the empty word is denoted with

Answer 3

ε (“epsilon”)

Question 4

if w and w’ are both words over Σ, then w·w’ is the word over Σ obtained by

Answer 4

concatenation of w and w’. We will often write just ww’ to abbreviate w·w’.

Question 5

for all words w, the concatenations εw and wε are

Answer 5

the same word w.

Question 6

A language over an alphabet Σ is

Answer 6

a subset of Σ*

Question 7

Consider the alphabet
Σ = {a, b, c, d},
and the set:
L = { a·w·a | w ∈ Σ∗ }

L contains:

Answer 7

all words that start with a, continue with 0 or more symbols in Σ, and end with a.

Question 8

L1 = {ε} is

L2 = ∅ is

Answer 8

L1 is the language that only contains the empty word ε;

L2 is the empty language, that does not contain any word.

Question 9

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

Answer 9

• Q is a finite set of states;
• Σ is a finite set of input symbols, called the alphabet;
• δ : (Q × Σ) → Q is the transition function (δ is the Greek letter delta);
• q0 ∈ Q is the initial state;
• F ⊆ Q is the set of final (or accepting) states.

Question 10

A non-deterministic finite-state automaton (NFA) is a 5-
tuple (Q, Σ, δ, q0, F) just like in DFA — with one difference:

Answer 10

δ ⊆ (Q × Σ) × Q is the transition relation.

Question 11

True or false all DFAs are also NFAs

Answer 11

True

Question 12

True or false all NFAs are also DFAs

Answer 12

False

Question 13

The main advantage of NFAs over DFAs is that

Answer 13

NFAs are more flexible and allow to define more compact automata, with less states and transitions