GentleRex
Induction example
Intro to Theory of Computation
Reg lang properties
Pumping Lemma
decidability and MORE..
   
 







"REG"-L
---Closed under UNION---

Simple!
(just add a few edges to connect!) while
this may appear to be an easy fix and can
approximate a solution in some cases- it is
not worthy of a complete proof (as again,it is
not comprehensive..

Following perhaps (example 1.11 in the book ((theory of
computation , by michael sipser)) ) you
can join two languages , but it is a special case
as either subset langauge starts with a different
letter - consider they were the same like the
following two languages
from {a,b,c} alphabet...
A1 "starting with an a followed by any number of b's,
then three 'c's and any number of a's.


A2 starting with an a followed by any number of 'c's,
then three a's and any number of b's etc...

 

you cannot be both deterministic and simply have two
paths from the same state to separate paths.


Remember! there is a deterministic solution to the
above A1,A2 union languages as they are both
regular!- however, simply joining the sub-graphs is not
it!


AGAIN - notice (and this will be the 'style' that I will be
adhering towards in solving / understanding our languages,
and their properties - as mentioned- it is not the easiest
solution that we use to represent our problem(s) it is rather
the more sophisticated / interesting problem that is needed to
emphasize the point. Our goal here is too understand the 'proof by
construction' presented on pp 45 /46 (sipser)


this is where we rely on the construction supported by the
suggestion of the catesian product

What in this case am i takin the cartesian product of ?
it is of the states represented by individual graph structures


consider two minimal languages towards our example....

(for brevity lets keep these really simple - how about a
one word language!)
over the alphabet of {a,b,c} ... these languages have an
individual word as there language

(why NOT KEEP THINGS SIMPLE FOLKS!)
A1  abbbc
A2  acbc


now what would our UNION of A1 U A2 language consider
(of course you know this!!)

(abbc, acbc)

 

A1

q1->'a'->q2->'b'->q3->'b'->q4->'b'->q5->'b'->q6->'c'->q7


A2

q8->'a'->q9->'c'->q10->'b'->q4->'c'->q11

 

I will have a new set of states (maybe I should have started with an
even smaller example!)


q1/q8, q1/q9, q1/q10, q1/q11
q2/q8, q2/q9, q2/q10, q2/q11
...
.
.
.

 


that is how #1 starts to look  - you have to consider everything...


#2 is straightforward with my example as you have the same alphabet
but lets say you had a second alphabet with e,f,g
then you would have a,b,c,e,f,g

#3 this says my output state will be equivalent to the individual output
states

insert (q1/q8 , 'a') in the left handside here....
(( in T((r1,r2),a) = (T(r1,a),T(r2,a))    ))
***** note .... i substituted 'T' for the greek transition symbol character!

this should take me to q2/q9 here!

 

more to come!


note that this can be easily modified to support intersection as
noted in (sipser) text.......