Построение НКА допускающего регулярное выражение (a+b)*(aa+bb)

Задание 1

Построить НКА допускающий регулярное выражение (a+b)*(aa+bb)

Построим (графически) НКА допускающий данное регулярное выражение.

Вполне очевидно, что язык допускаемый автоматом:

L = L₁L₂, где L₁ = {ωaa | ω{a,b}*}, L₂ = {ωbb | ω{a,b}*}

Мною была написана программа, определяющая принадлежит ли входная цепочка языку допускаемому автоматом. Реализована на языке проектирования PDL.

array data (N)

scalar i,j,flag,c

i:=0

j:=0

flag:=1

while c≠’.’ and flag=1

do

   [Считываем цепочку]

   if c≠’.’ and c≠’a’ and c≠’b’ then flag:=0 fi

   if c=’a’ or c=’b’ then data(i):=c

   i:=i+1

od

i:=i-1

[В итоге после этого цикла мы получим либо цепочку состоящую только из символов ‘a’ и ‘b, либо мы получим flag со значением равным 0 и значит наша цепочка явно не принадлежит языку допускаемому автоматом]

if flag=0 then ПЕЧАТЬ (Недопустимый символ в цепочке) fi

else

if i>=2 [Все цепочки входящие в язык допускаемый автоматом имеют длину > либо =2. Минимальные цепочки – это aa или bb]

if data(i-1)=’a’ and data(i-2)=’a’ or data(i-1)=’b’ and data(i-2)=’b’ then ПЕЧАТЬ (Допустимая цепочка) fi

else ПЕЧАТЬ (Недопустимая цепочка)

fi

else ПЕЧАТЬ (Короткая цепочка)