1: Regular languages and FSAs

Question 1

True/false: all finite languages are regular

Answer 1

True.

Question 2

What is an alphabet?

Answer 2

A finite set of symbols, called letters.

Question 3

What is a letter?

Answer 3

One item (symbol) within an alphabet.

Question 4

How do you use the pumping lemma to show a language is regular?

Answer 4

??

Question 5

If A is an alphabet, what is A*?

Answer 5

A* = the set of all words over (that can be built from) the alphabet A, including the empty word. Words are built from 0 or more letters from the alphabet. Languages from the alphabet A will be subsets of A*.

Question 6

How do you define a DFA?

Answer 6

You define DFAs as tuples of 5 items as M = (A, S, F, s0, T).
A = alphabet
S = set of states
F = transition function, which takes a non-empty input letter and current state and returns (and goes to) another state
s0 = start state; s0 ∈ S
T = set of accept states, aka terminals. T is a subset of all states: T ⊆ S.

Question 7

What is a terminal also known as?

Answer 7

A terminal is aka an accept state.

Question 8

What is a transition function?

Answer 8

Transition functions are used to translate between current states to the next ones according to inputs in FSAs.

Question 9

What is a regular language?

Answer 9

Languages are regular when there is a DFA whose language is the same as the language in question.

Question 10

What is an NFA?

Answer 10

A nondeterministic finite state automaton (NFA) is a variant of a FSA which can be modelled as being in more than one state simultaneously. Thinking of the current states of machines as brances of a tree, only one leaf node needs to accept at some point for the NFA to accept the input.

Question 11

How do you define an NFA?

Answer 11

You define NFAs as a tuple of 5 items such that M = (A,
S, F, s0, T).
A = alphabet
S = set of states
F = transition function, which takes an input letter (which can now also be empty) and current state and returns (and goes to) another state in the power set of S, P(S), which is the set of all subsets of S (since some may become cut off)
s0 = start state; s0 ∈ S
T = set of accept states, aka terminals. T is a subset of all states: T ⊆ S.

Question 12

What is the language defined by an NFA?

Answer 12

The language will consist of all the words that the NFA accepts.

Question 13

Prove that if a language is accepted by an NFA if and only if it is accepted by a DFA.

Answer 13

Let N = (A, S, F, s0, T) be an NFA. We construct a DFA M that accepts L(N). We let M = (A,P(S), F’, S0, T’), where:
• The transition function F’ : A x P(S) → P(S) is given by:
F’(a, X) = {y ∈ S : ∃ x ∈ X with a path labelled ϵ ^ i a ϵ ^ j = a from x to y in N, for some i, j ≥ 0}.
• The start state is S0 = {s0} ∪ {s : there exists a path labelled only with ϵs from s0 to s}.
• The new set of accept states is T’ = {Y ⊆ S : Y ∩ T ≠ ∅}, which is all sets of states containing at least one accept state of N.
To finish the proof, we need to show that L(M) = L(N). To do this, we first show that L(N) ⊆ L(M) and then that L(M) ⊆ L(N). To see that L(N) ⊆ L(M), let w = a1 a2 … an ∈ L(N). Then there is a path in N: S0 → a1 S1→ a2 S2 → ··· → an Sn ∈ T’.
Let S1 = F’(a1, S0), S2 = F’(a2, S1), …, Sn = F’(an, Sn-1). Then s1 ∈ S1, s2 ∈ S2, …, sn ∈ Sn ∈ T’. So there is a path in M: S0 → a1 S1 → a2 S2 → ··· → an Sn ∈ T’. So w ∈ L(M). Therefore L(N) ⊆ L(M).
We finish the proof by showing that L(M) ⊆ L(N). Let w = a1 a2 … an ∈ L(M). Then there is a path in N:
S0 → a1 S1 → a2 S2 → ··· → an Sn ∈ T’.
By definition of T’, there exists some sn ∈ Sn ∩ T. Hence there exists some sn-1 ∈ Sn-1 such that sn-1 → an Sn is a transition in N.
Continuing in this fashion, we eventually conclude that s0 ∈ S0 = {s0} and there exists a transition s0 → a1 s1 in
N.
Therefore we can conclude that in N there is the path:
s0 → a1 si1 → ··· → an sin ∈ T and so w ∈ L(N).

Question 14

How do you convert from a regular expression to an NFA?

Answer 14

1. To start, draw a diagram with two states – a start state s and an accept state t, with an arrow from s to t labelled with the whole regular expression. This diagram is not, in general, an NFA, but we will make it into one.
2. We slowly break down the labels on the arrows until each label is either a single
   letter or Ɛ. To break down an arrow labelled R1 R2, introduce 2 new arrows, R1 and R2, with the same start and end nodes.
3. To break down an arrow labelled R1R2, introduce a new intermediate state, s’, connected to from the first node with R1 and to the second node with R2.
4. To simplify an arrow labelled R*1 introduce a new state s’ with two epsilon connections from the first node and s’ and s’ to the second node, and with R1 being a connection from s’ to itself.
   Continue until each arrow is labelled by a single letter (or Ɛ). The resulting diagram will be of an NFA. It can then be turned into a DFA, if necessary, using the NFA to DFA conversion method.

Question 15

What is a regular expression?

Answer 15

A sequence of letters in a given pattern used to define a language in a compact manner.

Question 16

Why are the definitions of regular expressions recursive?

Answer 16

The empty word and all single letters are regular expressions. All concatenated pairs of regular expressions, unions of regular expressions, one or more concatenated copies of a regular expression are also regular expressions.
R1 R2 = R1 | R2 = R1 ∪ R2 = union of R1 and R2.
R1R2 = concatenation of R1 and R2.
R1* = one or more concatenated copies of R1, aka Kleene closure of R1.

Question 17

True/false: if L1 and L2 are languages over an alphabet A that are both defined
by regular expressions, then so are L1 ∪ L2, L1, L1 ∩ L2, L3 = {w ∈ A : w ∉ L1}
and L1 \ L2 = {w : w ∈ L1, w ∉ L2}.

Answer 17

True.

Question 18

Prove that if L1 and L2 are languages over an alphabet A that are both defined
by regular expressions, then so are L1 ∪ L2, L1, L1 ∩ L2, L3 = {w ∈ A : w ∉ L1}
and L1 \ L2 = {w : w ∈ L1, w ∉ L2}.

Answer 18

??

Question 19

What is Kleene’s theorem?

Answer 19

A language is described by a regular expression if and only if there is a DFA which defines it.

Question 20

What is the proof of Kleene’s theorem?

Answer 20

??

Question 21

How do you convert from an NFA to a regular expression?

Answer 21

Here’s a method to go from an NFA (A, S, F, s0, T = {t1,…,tk}) to a regular expression.
1. The first step is to add a new start state s, connected to s0 by a Ɛ-arrow.
2. Next, we add a new accept state, t, with a Ɛ-arrow from each state ti ∈ T to t, and turn each state ti 2 T into a non-accepting state.
3. Eliminate multiple arrows between any pair of states si and sj, R1, R2 .. Rn, into a single arrow R1 R2 … Rn going from si to sj.
4. To eliminate a state sj between si and sk, combine all arrows from si to sj, sj to sj, and sj to sk, R1, R2 .. Rn as a single arrow between si and sk R1 R2 … Rn
Repeat steps 3 and 4 until only states s and t remain, with a single arrow between them; that single will be labelled with the desired regular expression.

Question 22

What is the pumping lemma?

Answer 22

A set of moves that can be performed to show whether a language is regular or not. All sufficiently long words in any regular language can repeatedly have their middle sections repeated an arbitrary number of times - pumped - to make new words that will also lie within the same language.

Question 23

How do we show whether a language is regular?

Answer 23

??

Question 24

What is the proof of the pumping lemma?

Answer 24

??

Question 25

How does the pumping lemma work?

Answer 25

??

Question 26

How do you use the pumping lemma to show a language is not regular?

Answer 26

??

Question 27

Prove that all finite languages are regular.

Answer 27

If a language, L, is finite, there exists an alphabet A and w1, w2,…, wn ∈ A* such that L = {w1, w2,…,wn}. A regular expression for L is w1 w2 ··· wn. Since the language can be expressed with a regular expression, the language is regular.