Программирование Конечного Автомата (КА)

Конечным автоматом K называется всякая пятерка вида:

       KL=<X,Q,Q',q0',F> , где X - некоторый конечный непустой алфавит,  Q - множество состояний данного автомата, Q' - подмножество Q, называемое множеством заключительных состояний, q0' - элемент Q, называемый начальным состоянием автомата, - отображение F: X*Q->Q, называемое функцией переходов.

KL может распознавать некоторый язык L над X .

Вашему вниманию предоставляю следующую функцию для распознания принадлежности слова языку adna:

 


  1. function ada_check(s:string):boolean;
  2. var i:integer;ans:boolean;
  3. begin
  4.  
  5.      ans:=false;
  6.      if s[1]='a' then
  7.         if s[2]='d' then
  8.             for i:=3 to length(s) do begin
  9.                   if s[i]='d' then begin
  1.                       j:=i; while (s[j]='d') and (j&lt;=length(s)) do begin
  2.                               inc(j);
  3.                               if j&gt;length(s) then ans:=false
  4.                               else
  1.                                      if (s[j]='a') and (j=length(s)) then ans:=true;
  2.                    end;
  3.                   end;
  4.                  if s[i]='a' then if i=length(s) then ans:=true;
  5.                  if (s[i]&lt;&gt;'d') and (s[i]&lt;&gt;'a') then break;
  6.  
  7.             end;
  8.      if ans=true then writeln('the word ',s,' belongs to language')
  9.      else writeln('the word ',s,' does not belong to language');
  10.      readln; ada_check:=ans
  11. end;

Ну, я то знаю, что Вы

Ну, я то знаю, что Вы обучаемая и, главное, позитивная девушка! Но не очень-то и задавайтесь ;-).

Как реализовать оператор case

Как реализовать оператор case по символам? Ведь не получится, например, сделать

  1. case a of
  2.   'a': ...;
  3.   'd': ...;
  4.   ...
  5. end

Case. Почему не получится?

Case. Почему не получится? Селектор - это выражение любого ПОРЯДКОВОГО типа.

     Чтож, я

     Чтож, я претендую на всеобщность. Тогда я пришёл к выводу,
что case использовать неудобно. И, со всем уважением, сравнивать
с вашими функциями смысла нет: ведь для общего случая они не подойдут.
Насчёт языка: он всё тот же, 'a(d^n)a'.
     Итак, переход в следующее состояние зависит от текущего состояния
и от только что прочитанной буквы. Значит, надо построить отношение,
которое паре ('состояние','буква') ставит в соответствие 'состояние'.
Т.е. пусть 'Q'-это все возможные состояния, 'Alph'-это алфавит, зависящий
от языка, тогда надо построить отношение (Q,Alph)->Q.
     Обычно Alph есть подмножество Char. Тогда заводим двумерный массив
'array[Q,Char] of Q' ,который и заполняется в зависимости от языка.
Если символ не пренадлежит Alph, то значение массива для любого
состояния и этого символа будет соответствовать 'неуспешному'.
     Для нашего языка 'a(d^n)a' заполнить массив очень легко, а вот для
более сложных языков это серьёзная задача.
     Кстати, после всех изменений мой код стал, как мне кажется, проще
и понятней. Он работает для нашего языка, и при этом с помощью нехитрых
модификаций будет работать и для других. Главное- правильно построить
отношение (Q,Alph)->Q.
     Итак, алгоритм тот же.
              База рекурсии: слово пусто, и в зависимости от текущего состояния даем ответ;
              Шаг рекурсии: отсекаем первую букву слова, и в зависимости от текущего состояния и этой буквы повторяем все
                                       с новым состоянием и с полученным словом.

<pre>
program Ada

const
    max=4; //число 'max' определяет общее кол-во состояний
    unsuccessful=max; //пусть 'max' будет неуспешным состоянием
    successful=max-1; //пусть 'max-1' будет успешным состоянием
    {строго говоря, для других языков успешных состояний может быть больше одного}
type
    Q=0..max; //'Q'-это все возможные состояния
    Mass=array[Q,Char] of Q;
    {паре ('состояние','буква') ставится в соответствие 'состояние'.
    Все состояния Q, кроме 0, successful и unsuccessful являются рабочими}

var
    m:Mass;
    s:string;
    ans:boolean;

procedure ini(var m:Mass);
var
    i:Q;
    j:Char;
begin
    for i:=low(i) to high(i) do begin
      for j:=low(j) to high(j) do begin
        m[i,j]:=unsuccessful; //весь массив заполняем неуспешным состоянием
      end
    end;
    {теперь самое сложное (но не для нашего языка): строим отношение (Q,Alph)->Q }
    m[0,'a']:=1; //если первая буква 'a', то переходим в рабочее состояние 1
    m[1,'d']:=2; //если последующие буквы 'd', то переходим..
    m[2,'d']:=2; //.. и остаемся в рабочем состоянии 2
    m[2,'a']:=successful; //если буква 'a', то в успешное состояние, у нас это 3
    {любой иной случай ведет в неуспешное состояние, которое у нас равно 4}
end;

procedure check(k:Q; var s:string; var m:Mass; var ans:Boolean);
var
    a:Char;
begin
    if s<>'' then
                 begin //если s непусто, то..
                    a:=s[1]; //.. определяем первую букву..
                    delete(s,1,1); //.. отсекаем её от s..
                    check(m[k,a],s,m,ans)
                  {..вызываем check для состояния m[k,a] и полученного слова s}
                 end
               else
                 begin //иначе..
                     if k=successful then ans:=true //.. если успешное, то 'да'..
                                             else ans:=false //.. в любом ином состоянии- 'нет'
                 end;
end;

begin
    {здесь всё понятно, надеюсь :)}
    ini(m);
    readln(s);
    check(0,s,m,ans);
    if ans then writeln('yes')
              else writeln('no');
end.
</pre>

     Если же у вас свой язык, то надо изменить значение max, подумать над числом
'успешных' состояний, а так же переопределить отношение (Q,Alph)->Q. Всего-то делов:)

     P.S.:то ли я дурак, то ли теги не работают.

Теги действительно пока не

Теги действительно пока не работают. Я, как раз, кое-что сейчас меняю. А с Вами, Илья, уверен, всё впорядкеWink

Да, работает case, это я

Да, работает case, это я что-то намудрила )

Скажите, пожалуйста, Илья или

Скажите, пожалуйста, Илья или В.Ш., такого вида отношения проходят на 2-ом курсе или по ОСМ на 1-м(что-то не припомню, видимо, упустила)?

Что если в процедуре check

Что если в процедуре check сделать условие if (s <> '') and (k <> unsuccessful) then ... для того, чтобы не проходить "неверное" слово до конца, а остановиться, если встретится неверная буква?

Вот вариант общего описания

Вот вариант общего описания решения Ильи в форме распознавателя-функции:

  1.    //Q - алфавит состояний, X - алфавит входных символов
  2.    const QLim=...      //число состояний -1    
  3.    type TQ=0..QLim;// тип состояний
  4.            
  5.            TX='a'..'z'; //тип символов
  6.            Var qx: array[TX,TQ] of TQ; // матрица переходов
  7.                   finalSet: Set of TQ; // множество заключительных  состояний
  8.    ...        
  9.    function Ok_check(q:TQ; s:string): Boolean;
  10.    Begin
  11.        If s=''  then
  12.               Ok_check:= (q in finalSet)
  13.        Else
  14.               Ok_check:= Ok_check(qx[s[1],q], Copy(s, 2, Length(s)-1)):
  15.   End;  

if (s <> '') and (k <>

if (s <> '') and (k <> unsuccessful) then .... - не отвечает определению распознавания языка КА.

Кхм... Не доходит... Почему

Кхм... Не доходит... Почему не отвечает? Работает... Да, мне не достает теории.

Да, Наташа, Вам

Да, Наташа, Вам действительно, очень мягко говоря, "не достаёт теории", которая систематически была изложена для 2-го курса . Извините, но больше говорить я с Вами на эти темы не буду...

Максим, желание и умение

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