ex1
w, u and v are strings
T is an alphabet
A and B are languages
1.What is the value of |λ| ?
0
2.What can you say about λw and wλ?
They are equal
3.What is the relationship between |uv|, |u| and |v| ?
|uv| = |u| + |v|
4.State a necessary and sufficient condition on T for T* to be finite. If T* is finite, list its members.
T = {}
T* = {λ}
also!
T = {λ}, T* = {λ, λλ, λλλ, λλλλ, ... } == T* = {λ}
5.Give an example to show that uv = vu is not always true.
Give a non-trivial example to show it is not always false.(in this case trivial means an example using λ)
if u = ab & v = ba, u ≠ v
if u = v this is a sufficient but unnecessay condition since
u = a & v = aaaa ∴ uv = aaaaa and so uv = vu. u = v is too strong a condition ie needs to be more flexibile as |u| could be greater, less than or equal to |v| if T = {a} ie if b ∉ T
6.Give necessary and sufficient conditions on u and v for uv = vu.
The way to generalalise this is to say that u = x* and v = x*
Since v can be a substring of u ie u = abab & v = ab
but this is a weak conidition as u = abab & v = b clearly not working
so make x a string –
for uv = vu; u = w* & v = w*
making this a necessary and sufficient case.
7.List all the (i) prefixes, (ii) suffixes, and (iii) substrings of abb.
prefixes {λ, a, ab, abb}
suffixes {λ, b, bb, abb}
substrings { λ, a, b, ab, bb, abb}
notice: prefixes ∪ suffixes = substrings
“being a prefix is a sufficient condition in order for it to be a substring” // implication
prefix → substring
“if it is a prefix it is necessary that it is a substring”
prefix ↔ substring
8.If A = {a, ba} and B = {a, λ, bb}, list, in lexical order, the elements of (i) A+B and (ii) AB, and the first 12 strings in A*.
9.Which ordering scheme (dictionary or lexical) is most useful for infinite sets, and why?
(give an example of the first 10 elements of some infinite language in both orderings, to illustrate the advantage of one scheme)
For an ordering to be lexical, all characters will be rendered in finite time.
10.Under what conditions are A* and A+ equal?
A = {λ, a, b}
λ ∈ A
11.If T has only two symbols, show that every string over T of length 4 or more must have two adjacent non-empty equal substrings.
(hint: for starters you can write out all of the strings of length four and see if it is true for them)
for || = 4
aa aa |substring| = 2——a a ab |ss| = 1 – -
a a ba – -
aa bb——ab a a
– -a b b a – -
ab ab——ab b b
– -the above works for |w| > 4 since you take the above and add one character to it.
for |w| = 3, take the case aba. There are no adjacent similiarities.
12.Let T be the alphabet {a,b,c}, and λ be the empty string.
(i)Write down the first five elements of T* in lexical order and dictionary order.
13.If I have a machine with 1GB of memory, how many possible states can the machine be in?
2233
What is infinity?
a member of the set of integers?
{0, 1, 2, 3, 4, ∞}
no! since each element of this set is finite, and the largest element of this set is undefined
Now, how would you show the infinite language of all words that start with the letter a, with any number of a’s and b’s following?
T+ = {a, aa, ab, aaa, aba, abb, aab, etc}
a*b*a* ... ?
The answer is: a(a+b)*, where + means a orb, zero or one or many times.
a 5-tuple FSA : Q = 2; T = {a,b} I = q0; F = q1; E = {{q0, a, q1},{q1, a, q2},{q1, b, q2}}
This way, an infinite language can be defined and its regular since no number has to be stored; if we had anbn ie to define a language with equal number of a’s as b’s, then you would have an irregular language; there would have to be a comparison between the n of the a and be n of the b.
So, though the number 22^33 is very large if all the memory you had was 1Gb, any number larger than that could store would break the limit.
What is the connection between the limit of space and a regular language?
Regular languages define infinite sets like T* and a finite number of states … what?
