Aalborg den 18.02.2003

Leksikalsk analyse vejledende løsninger

Apple 2.1

Se Java kilde koden Appel2_1.java for at afprøve dine regulære udtryks løsninger i Java.

Appel 2.2

Appel 2.4

Se pdf filen appel2_4.pdf.

Appel 2.5

a) closure(s1)={1,2,3,4} dette er den nye start tilstand. Transtions tabellen er vist nedenfor.

state x y z
{1,2,3,4} {5,6,7} {6,7}
{5,6,7} {6,7}   {1,2,3,4}
{6,7}      

b) closure(s1)={1} dette er den nye start tilstand. Transtions tabellen er vist nedenfor, her nærmere vi os exponential blowup.

state a b
{1} {1,2} {1}
{1,2} {1,2,3} {1,3}
{1,2,3} {1,2,3,4} {1,3,4}
{1,3} {1,2,4} {1,4}
{1,2,3,4} {1,2,3,4,5} {1,3,4,5}
{1,3,4} {1,2,4,5} {1,4,5}
{1,2,4} {1,2,3,5} {1,3,5}
{1,4} {1,2,5} {1,5}
{1,2,3,4,5} {1,2,3,4,5,6} {1,3,4,5,6}
{1,3,4,5} {1,2,4,5,6} {1,4,5,6}
{1,2,4,5} {1,2,3,5,6} {1,3,5,6}
{1,4,5} {1,2,5,6} {1,5,6}
{1,2,3,5} {1,2,3,4,6} {1,3,4,6}
{1,3,5} {1,2,4,6} {1,4,6}
{1,2,5} {1,2,3,6} {1,3,6}
{1,5} {1,2,6} {1,6}
{1,2,3,4,5,6} {1,2,3,4,5,6} {1,3,4,5,6}
{1,3,4,5,6} {1,2,4,5,6} {1,4,5,6}
{1,2,4,5,6} {1,2,3,5,6} {1,3,5,6}
{1,4,5,6} {1,2,5,6} {1,5,6}
{1,2,3,5,6} {1,2,3,4,6} {1,3,4,6}
{1,3,5,6} {1,2,4,6} {1,4,6}
{1,2,5,6} {1,2,3,6} {1,3,6}
{1,5,6} {1,2,6} {1,6}
{1,2,3,4,6} {1,2,3,4,5} {1,3,4,5}
{1,3,4,6} {1,2,4,6} {1,4,5}
{1,2,4,6} {1,2,3,5} {1,3,5}
{1,4,6} {1,2,5} {1,5}
{1,2,3,6} {1,2,3,4} {1,3,4}
{1,3,6} {1,2,4} {1,4}
{1,2,6} {1,2,3} {1,3}
{1,6} {1,2} {1}
{1,2,3,4,6} {1,2,3,4,5} {1,3,4,5}

c) closure(s1)={1,5,10,11} dette er den nye start tilstand. Transtions tabellen er vist nedenfor.

state a c r s t
{1,5,10,11} {2,6,11,15}
{2,6,11,15} {3,7,12,16}        
{3,7,12,16}     {3,7}   {4,8}
{3,7}       {18}  
{4,8}       {9}  
{18}          
{9}          

Venlig hilsen
Kristian Torp