Hello everyone.
I am the teaching assistant for
this course.
Today I will host
a second problem session.
We will discuss several topics,
which cause confusion, in some students.
And this will include Kleene Star and
paths in the DFA.
Then, we will show the solution for
first challenge problem.
Let's begin with Kleene Star.
Kleene Star is an operation
on regular expressions.
For example, we can have one star, where
one is a regular expression of length one.
However, there is a common
misconception that one star is
an infinite long string of ones.
This is not the case.
In fact, one star is still a regular
expression who's language,
L(1*) is the set of strings of zero or
more ones.
Although, this set is infinite,
each element in it has finite length.
This is similar to the set of integers,
where the set is infinite, but
each element it contains is finite.
Now we're coming to
the topic of infiniteness.
As we know, infinite objects
are important in mathematics,
like the set of integers or a line that
contains an infinite number of points.
Yet, in a computational model, a computer
can never get an infinite input,
unless, you can represent
it in finite form.
For example,
we can represent a regular language
with a regular expression
which has finite length.
We can also store three numbers
as parameters for a line.
In such cases,
we extract important information
that can represent the whole set.
This concept is a bit like sufficient
statistics, in case you have heard of it.
Now, we will take a minute to discuss
a fallacy we found in the forum.
In the thread, it talks about a DFA
that accepts all strings of 0's and
1's, except those whose
last character is 1.
Then a student asks,
what about the string 1?
Basically sometimes, we fall into
the fallacy that you cannot have
a last character unless you have
other characters, this is not true.
In fact, if we resort to strict
mathematics, we will define that for
n greater than or equal to 1,
the last character of any string a 1,
a 2 through a n, is just a n, period.
Thus coming back to the question.
The string 1is not accepted by this DFA,
because the last character is 1.
Another thing worth mentioning,
is that the anti-string
epsilon has no last character.
Thus the statement is last
character is 1 is false.
So epsilon is accepted by the DFA.
We will now start to discuss
the conversion from a DFA into
a regular expression.
Firstly, let's have a review,
In the conversion, we introduced
the notion of k-path induction.
Where Rijk is the regular expression for
the set of labels of k-paths
from state i to state j.
This means that starting from i,
if the DFA receives any string from Rijk,
it will go to state j.
And we'll not pass any node,
with label greater than k.
And Rijk describes all such strings.
In the lecture, we gave a way of
computing Rijk, which is either
via not going through state k, or
going through k one or more times.
This give us a formula.
R ij k, is R ij
k-1 or R ik k-1.
R kk k-1*.
And Rkj, k-1.
Now, let's take a closer look.
In the illustration,
we can see that Rik, k-1,
corresponds to the part from i,
to the first encounter of k.
Then all parts between k can
be described by Rkk, k-1.
As we do not know how many times the pad
will go through k, we use Rkk, k-1*.
In the end, we have Rkj, k-1.
Which corresponds to the label of path
from the last encounter of k to j.
Here we point out that the labels of
the path from the first encounter
of k to the last can also
be represented by Rkk k.
Because it is just a path from
k to k going through now with,
with labels not greater than k.
And in each cases, both Rkk, k-1 star,
and Rkk, k contain epsilon,
the empty string.
In spite of the equivalence, we pick Rkk,
k-1* because this will give us a formula
where quantities with a higher
super script will always only depend
on quantities with lower super script.
Which makes the implementation and
understanding much easier.
Lastly, we will show our solution
to the first challenge problem.
The problem says that L is a language
with alphabet 0, 1 and 2.
L contains no strings that
have three consecutive 0's,
three consecutive 1's or
three consecutive 2's.
For example,
the string 11000220 is not in L.
Because it contains three consecutive 0's.
The task is to prove that L is regular and
then give a DFA for L.
Firstly, we can prove that,
the complement of L has a regular
expression, which is in this form.
We have three consecutive 0's,
or 1's, or 2's,
with any number of 0's, 1's,
and 2's before and after.
This record expression exactly
defines all strings that do
contain three consecutive 0's,
or 1's, or 2's.
Additionally, we have the nice
property that regular languages.
Are closed under complement.
So it follows that l
the complement of the language of
this regular expression is regular.
To construct a DFA for L,
it turns out that we can directly do it,
without the trick of union or complement.
We define the state to represent the run
of the same symbol that appears at
the end of the string.
Specifically, we will have
start state S which we
enter only initially when the input
stream so far is epsilon.
Then we have state a 0, a 00, a 1, a 11,
a 2, and a 22, and a dead state D.
The intent is that if the current string
redding contains any three consecutive
0's, or 1's, or 2's,
the DFA will fall into D and stay there.
Otherwise, say the string
has ending 012011.
The DFA should go to state a11
because it denotes that the string
has two ones at the end.
Here is the final transition table for
the DFA of L.
Note that whenever we already have
two 0's, which is described by A00,
an addition of 0 will kick
the DFA into the depth state D.
But character 1 or
2 will shift the state to a1 or a2.
As now the longest run of symbols at
the end is a single 1 or a single 2.