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

Конечным автоматом 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;

Главная программа может

Главная программа может выглядеть след. образом:

program ada;
var f:file of char;c:char;str,path:string;b:boolean;

procedure get_word(var w:string);
begin
      w:='';
      while (c<>' ') and (not(eof(f))) do begin
            w:=w+c;read(f,c);
      end;
end;

 begin
       write('enter the path of text-file: ');readln(path);
       assign(f,path);
       reset(f);
       while not(eof(f)) do begin
                 read(f,c);
                 get_word(str); // процедура считывания слова из текста в переменную str (слова разделены пробелом)
                 b:=ada_check(str);
                if b=false then begin writeln('error. unkown word');break;end;
       end;
       writeln('the text is good :)');readln;
end.

Я в этом, конечно, ничего не

Я в этом, конечно, ничего не понимаю, но если слово будет addddd...., т.е. без а на конце, то оно тоже пройдет проверку и ans будет true. А если, например, будет слово adsdfgba, то ans также будет true. Я так понимаю, что слова должны быть вида addd...ddda? Если да, то, наверно, лучше сделать break, если вдруг ans = false.

ну как же не понимаешь!! во

ну как же не понимаешь!! во как определила все))

уже учел, спасибо)) говорю ж - спешу))

1. Если материал размещается

1. Если материал размещается на сайте, то это ответственно. Спешка не уместна. Ошибки должны быть исключены (этому поможет отладка и  тестирование).

2.Неряшливая структура программы (в частности, отсутствие  отступов и  группирующих операторных скобок) не способствуют желанию в неё вникать.

Это, Адам, Вы получили по

Это, Адам, Вы получили по заслугам! Причём, от "малышни"Laughing. Наука. Лучше ничего не писать, чем так подставляться...

Да дело в том, что я поняла

Да дело в том, что я поняла только процедуру. Главную программу не поняла совсем. Для меня это темный лес Laughing

(Тема не указана)

Embarassed

Объясни мне, пожалуйста, что

Объясни мне, пожалуйста, что за тип такой file of char и что делают assign, reset и eof?

текстовый файл.. вообще, тебе

текстовый файл.. вообще, тебе будет интереснее проходить это на лекцииWinkSmile

Ну, текстовый файл - это уже

Ну, текстовый файл - это уже что-то. Smile Что-то мне не понятна процедура get_word. Когда ты пишешь get_word(str) разве str чему-то равно? И это не понятное значение передается в локальную переменную w, которая тут же затирается. Но ты пишешь var перед w, что мне опять же не понятно. Ведь w - это только локальная переменная, в главной программе ее не существует. Короче, я запуталась Undecided

var в заголовке, как бы, дает

var в заголовке, как бы, дает непосредственный доступ к самой переменной str через переменную w. надеюсь, корректно выразился)) подожди, как до подпрограмм дойдете все станет ясноSmile

Да, Адам. На этот раз, Вы не

Да, Адам. На этот раз, Вы не так уж плохо и объяснили. А Наташа забыла (скорей, не успела усвоить), что параметры подпрограмм бывают входные и выходные (отмеченные в заголовке описания словом  Var). Так вот, w - выходной параметр, он и не должен иметь значение в момент старта процедуры. Именно, сама процедура и формирует его значение из символов считываемого файла, после чего передаёт это значение фактическому параметру str. Это похоже на Read(str).

"Текстовые" файлы.

"Текстовые" файлы.

Запомните, Адам и Вы, Наташа, раз уж спрашиваете. Текстовый файл в своём определении всегда имеет ключевое слово TEXT. Конструкция вида file of T определяет, так называемый типизированный файл, состоящий из элементов (записей) типа T.

Поэтому "var f: file of Char"  определяет f как типизированный файл (состоящий из ASCII-знаков).

 

Спасибо. Теперь уже больше

Спасибо. Теперь уже больше понятно. Надо мне еще почитать что-нибудь на эту тему Smile

Что делать, если функция

Что делать, если функция eof(f) возвращает true, если в тексте находится одна буква? Или в не зависимости от того сколько символов в тексте, последний символ не берется в расчет?

Моя программа работает, но

Моя программа работает, но последняя буква не берется в расчет!

Наташа, покажите код, где

Наташа, покажите код, где "eof(f) возвращает true, если в тексте находится одна буква"

Вот вся программа: program

Вот вся программа:

  1. program ada;
  2.  
  3. {$APPTYPE CONSOLE}
  4.  
  5. uses
  6.   SysUtils;
  7.  
  8. var
  9.   f: Text;
  10.   c: Char;
  11.   str, path: String;
  12.   b: Boolean;
  13.  
  14. function Ada_check(s: String): Boolean;
  15. var
  16.   i: Integer;
  17.   ans: Boolean;
  18. begin
  19.   ans := false;
  20.   if (Length(s) >= 3) and (s[1] = 'a') and (s[2] = 'd') and
  21.       (s[Length(s)] = 'a') then
  22.   begin
  23.     ans := true;
  24.     for i := 3 to (Length(s) - 1) do
  25.     begin
  26.       if (s[i] <> 'd') then
  27.       begin
  28.         ans := false;
  29.         break;
  30.       end;
  31.     end;
  32.   end;
  33.   if ans then
  34.     Writeln('The word ', s, ' belongs to language')
  35.   else
  36.     Writeln('The word ', s, ' does not belong to language');
  37.   Readln;
  38.   Ada_check := ans;
  39. end;
  40.  
  41. procedure Get_word(var w: String);
  42. begin
  43.   w := '';
  44.   while (c = ' ') do
  45.     Read(f, c);
  46.   while (c <> ' ') and not(eof(f)) do
  47.   begin
  48.     w := w + c;
  49.     Read(f, c);
  50.   end;
  51. end;
  52.  
  53. begin
  54.   c := ' ';
  55.   b := false;
  56.   Write('Enter the path of text-file: ');
  57.   Readln(path);
  58.   Assign(f, path);
  59.   Reset(f);
  60.   while not(eof(f)) do
  61.   begin
  62.     Get_word(str);
  63.     b := Ada_check(str);
  64.     if (b = false) then
  65.       break;
  66.   end;
  67.   Close(f);
  68.   if b then
  69.     Writeln('The text is good :)')
  70.   else
  71.     Writeln('Error. Unkown word');
  72.   Readln;
  73. end.

Наташа, мне это всё настолько

Наташа, мне это всё настолько не нравится по стилю, что я даже вникать не хочу...
Оставьте это 2-му курсу. Экзамен им сдавать. Давайте займёмся своими делами, которых начать и кончить ...

Создаю файл с содержимым: ada

Создаю файл с содержимым: ada adddddda adda. Отвечает:
The word ada belongs to language
The word adddddda belongs to language
The word add does not belong to language
Error. Unkown word.
Создаю файл с содержимым: adaa. Все отлично. The text is good.
Файл с содержимым: а.
The word does not belongs to language
Error. Unkown word.
Если файл пустой, то просто
Error. Unkown word

Это происходит из-за того,

Это происходит из-за того, что если в файле после последнего слова нет пробела, выходит из цикла wile не присоединив последнюю считанную букву. И чтобы так не было нужно после цикла while добавить: if eof(f) and (c <> ' ') then w := w + c;
И тогда все заработает.

Спасибо! Действительно,

Спасибо! Действительно, работает. Надеюсь, Адам простит мне то, что за основу я взяла его программу, а не писала заново свою. Для меня эта тема не знакомая и не до конца понятая. Программа получилась очень большая. Это нормально для такой задачи или я все слишком усложнила?
Валерий Шахомболетович, что Вы подразумеваете под стилем и что Вам не нравится? Укажите, пожалуйста, на ошибки, буду исправляться.

На языке prolog все это

На языке prolog все это сделать и легче, и понятнее. Так что я попытался применить в pascal преимущества декларативных языков,
проще говоря, использовал рекурсию. Не скажу, что все стало намного понятнее и проще, но если бы язык был намного сложнее, чем
данный, то думаю, что реализация распознания принадлежности слова действительно упростилась бы.
Алгоритм
База рекурсии: слово пусто, и в зависимости от текущего состояния даем ответ;
Шаг рекурсии: отсекаем первую букву слова, и в зависимости от текущего состояния и этой буквы повторяем все
с новым состоянием и с полученным словом.

  1.    program
  2.      var s:string;  
  3.       ans:boolean;
  4.  
  5.   procedure q(i:byte;var s:string;var ans:boolean);
  6.              {i-текущее состояние
  7.               0-первоначальное
  8.               1,2-рабочие
  9.               3-успешное
  10.               4-неуспешное
  11.                                     s-часть заданного слова, соответствующее
  12.                                        текущему состоянию
  13.                                                          ans-результат:да или нет}
  14.   var  a:string;
  15.        k:byte;    //в какое состояние переходим
  16.      begin
  17.          if s<>'' then a:=s[1] //читаем первую букву текущей части слова
  18.                   else a:='';  //слово пусто(т.е. достигнута база рекурсии)
  19.          delete(s,1,1);        //отсекаем первую букву текущей части слова
  20.              case i of         //в зависимости от текущего состояния...
  21.                      0:begin
  22.                            if a='a' then k:=1 //если первая буква слова есть 'a', то идем в состояние 1
  23.                                     else k:=4 //иначе в 'неуспешное'
  24.                        end;
  25.                      1:begin
  26.                            if a='d' then k:=1 //если последующие буквы - 'd', то остаемся в состоянии 1
  27.                                     else begin
  28.                                            if a='a' then k:=2 //если же буква 'a', то идем в состояние 2
  29.                                                     else k:=4 //иначе в 'неуспешное'
  30.                                     end;
  31.                        end;
  32.                      2:begin
  33.                           if a='' then k:=3  //если слово закончилось, то идем в 'успешное'
  34.                                   else k:=4  //иначе в 'неуспешное'
  35.                        end;
  36.                      3:begin
  37.                            k:=3  //остаемся в текущем состоянии
  38.                        end;
  39.                      4:begin
  40.                            k:=4 //остаемся в текущем состоянии
  41.                        end;
  42.               end;{case}
  43.               case k of   //в зависимости от состояния, в которое нужно перейти...
  44.                     1,2:q(k,s,ans); //если k - 'рабочее' состояние, то вызываем процедуру q для состояния k и слова s
  45.                       3:ans:=true;  //если k - 'успешное' состояние, то отвечаем 'да'
  46.                       4:ans:=false; //если k - 'неуспешное' состояние, то отвечаем 'нет'
  47.               end;{case}        
  48.      end;{procedure}
  49.  
  50.  begin
  51.       readln(s);  //читаем слово
  52.       q(0,s,ans);  //вызываем процедуру q для начального состояния 0 и слова s...
  53.       if ans then writeln('да')      //... и отвечаем на вопрос :)
  54.                else writeln('нет');
  55.  end;
  56.  
  57. end.

Проверки показали, что программа работоспособна:)
P.S.: когда пишу комментарий, то соблюдаю отступы и т.п., а вот результат такой. Как исправить?

Используй теги <code>

Используй теги <code> или <pre>

Погоди, а зачем в case i of

Погоди, а зачем в case i of нужны 3 и 4? Ведь они никогда не выполнятся, потому что процедура q вызывается только в том случае, если i = 1, i = 2. И в самом начале, когда i = 0. Вообще, прикольное решение. :))

Я думаю, что все стало на

Я думаю, что все стало на много понятнее и проще! ;-)

Слово 'тэги' для меня

Слово 'тэги' для меня потемки, а их описание в ссылке к комментариям меня не просветило. Можно наглядно показать, что да как?

Чтобы разместить код тебе

Чтобы разместить код тебе нужно написать < pre >код< /pre >, но без пробелов между знаками больше-меньше и pre. Я поставила пробелы, потому что если напишу все как надо, то они и будут восприниматься как теги, и просто-напросто не отобразятся. Попробуй. А еще можно сделать так: < code >твой код< /code >. Опять же без пробелов.

Вот, Наташа несколько

Вот, Наташа несколько замечаний по стилю (и не только!) хотя бы в первой подпрограмме не понравившегося мне кода:
1. Вместо ... (s[1] = 'a') and (s[2] = 'd') and ... (а что если обязательный префикс был бы совсем длинный?) следовало бы писать: Pos('ad',s)=1;
2. Первый оператор for я бы заменил на конструкцию типа:

  1.  
  2.     i:=3;
  3.     While a[i]='d' do Inc(i);
  4.     ans:=(i = length(s) );

3. Операторы ввода-вывода, а тем более, приостановки в подпрограммах обычно не размещают (ну, разве что в целях отладки, что, видимо, и имеет место в Вашем случае).
4. Имя функции в теле её описания, но только в левой части операторов присваивания, использовать, конечно, можно всегда.
С учётом этих замечаний, получим:
  1. function Ada_check(s: String): Boolean;
  2.     var i: Integer;
  3. begin
  4.     Ada_check:=False;
  5.     If (Length(s) >= 3) and (Pos('ad',s)=1) and  (s[Length(s)] = 'a')  then Begin
  6.           i:=3;
  7.           While a[i]='d' do Inc(i);
  8.           Ada_check:=(i = length(s) )
  9.     End
  10. End;

Итого, 10 строк кода против Ваших 26-ти. Обратите внимание, здесь я использую линейный поиск с барьером!
И ещё совет (из моих наблюдений за Вашими реализациями) - не увлекайтесь расстановкой флагов и операторов Break. Это не способствует улучшению читабельности и ясности кода, а наоборот. Часто While справляется с ситуацией лучше и элегантней, чем пара for-break (хотя последняя и безопасней).
Критику остальной части Вашей программы оставим на потом.

Мне почему-то казалось, что с

Мне почему-то казалось, что с for и break быстрее. Напрасно мне так казалось. Надо мотать на ус :)

Как может быть быстрее, если

Как может быть быстрее, если нужны 2 проверки:
1. На предельное значение параметра цикла;
2. На условие досрочного выхода по break
Ну а "барьер" Вы увидели?

Барьером является то, что

Барьером является то, что однозначно встретится не существующая a[i] либо некоторая a[i] не будет равна 'd'.

И еще вопрос: почему когда

И еще вопрос: почему когда тип переменной f был file of char символы из файла читались неправильно? Я включила пошаговую отладку и увидела, что вместо 'a' читается какой-то квадрат, а вместо 'd' смесь из цифр и символов. Когда я переменила тип на Text все стало правильно читаться.

С барьером, вижу, понято. А с

С барьером, вижу, понято. А с файлами, - я в который уже раз, настоятельно советую оставить их пока в покое. До конца неосознанное применение того, что и само по себе не вполне понятно, с моей точки зрения - признак непрофессионального подхода к освоению профессии и, по крайней мере, у меня, уважения вызывать не может. На темы файлов и другие, не имеющие прямого отношения к предстоящим экзаменам темы, я говорить не буду. Пожалуйста, цените и своё, и моё время.

Илья! Вы разобрались с

Илья! Вы разобралиссь с тегами?

Теоретически да. Хотелось бы

Теоретически да. Хотелось бы исправить всё то, что я написал без тегов, но не знаю как. Или надо создать новый комментарий?

Если в том комментарии,

Если в том комментарии, который хочешь изменить, рядом с "ответить" есть "изменить", то можешь изменить. Иначе создавай новый комментарий.

Давайте продолжим дело,

Давайте продолжим дело, начатое Наташей.
Для начала наберите:
< pre >
Writeln('Test');
< /pre >

и покажите это нам, но, уберите из этого текста 4 умышленно мною сделанных пробела: 2 пробела - после знаков "<" и 2 пробела - перед знаками ">"

Writeln('Test'); Обидно, что

  1. Writeln('Test');

Обидно, что нельзя исправить...

Вы научились, уже и это хорошо ...

Вы научились, уже и это хорошо ...

Я прошу прощения! Но у меня

Я прошу прощения! Но у меня не интернет, а какой-то ослик: медленный и упрямый. Меня это так раздражает, что уже сил нет. Так что ещё раз на всякий пожарный извиняюсь...

А я-то подумал, реакция ...

А я-то подумал, реакция ... Ну, совсем не спортивная :))

Вопрос: что хорошо, а что не

Вопрос: что хорошо, а что не очень в коде? ( Могу спросить, ведь он стал более-менее читаем :-) )

На языке prolog все это сделать и легче, и понятнее. Так что я попытался применить в pascal преимущества декларативных языков,
проще говоря, использовал рекурсию. Не скажу, что все стало намного понятнее и проще, но если бы язык был намного сложнее, чем
данный, то думаю, что реализация распознания принадлежности слова действительно упростилась бы.
Алгоритм
База рекурсии: слово пусто, и в зависимости от текущего состояния даем ответ,либо же пришли в неуспешное состояние;
Шаг рекурсии: отсекаем первую букву слова, и в зависимости от текущего состояния и этой буквы повторяем все
с новым состоянием и с полученным словом.

  1. program
  2. var
  3.     s:string;
  4.     ans:boolean;
  5.  
  6. procedure q(i:byte;var s:string;var ans:boolean);
  7.                   {i-текущее состояние
  8.                    0-первоначальное
  9.                   1,2-рабочие
  10.                    3-успешное
  11.                    4-неуспешное
  12.                                     s-часть заданного слова, соответствующее текущему состоянию
  13.                                                        ans-результат:да или нет}
  14. var
  15.           a:string;
  16.            k:byte; //в какое состояние переходим
  17. begin
  18.       if s<>'' then a:=s[1] //читаем первую букву текущей части слова
  19.                  else a:=''; //слово пусто(т.е. достигнута база рекурсии)
  20.       delete(s,1,1); //отсекаем первую букву текущей части слова
  21.                 case i of //в зависимости от текущего состояния...
  22.                        0:begin
  23.                                      if a='a' then k:=1 //если первая буква слова есть 'a', то идем в состояние 1
  24.                                                  else k:=4 //иначе в 'неуспешное'
  25.                           end;
  26.                        1:begin
  27.                                      if a='d' then k:=1 //если последующие буквы - 'd', то остаемся в состоянии 1
  28.                                                 else
  29.                                                    begin
  30.                                                          if a='a' then k:=2 //если же буква 'a', то идем в состояние 2
  31.                                                                      else k:=4 //иначе в 'неуспешное'
  32.                                                    end;
  33.                           end;
  34.                       2:begin
  35.                                      if a='' then k:=3 //если слово закончилось, то идем в 'успешное'
  36.                                                else k:=4 //иначе в 'неуспешное'
  37.                          end;
  38.                end;{case}
  39.                case k of //в зависимости от состояния, в которое нужно перейти...
  40.                      1,2:q(k,s,ans); //если k - 'рабочее' состояние, то вызываем процедуру q для состояния k и слова s
  41.                         3:ans:=true; //если k - 'успешное' состояние, то отвечаем 'да'
  42.                         4:ans:=false; //если k - 'неуспешное' состояние, то отвечаем 'нет'
  43.                end;{case}
  44. end;{procedure}
  45.  
  46. begin
  47.      readln(s); //читаем слово
  48.      q(0,s,ans); //вызываем процедуру q для начального состояния 0 и слова s...
  49.          if ans then writeln('да') //... и отвечаем на вопрос :)
  50.                   else writeln('нет');
  51. end.

Проверки показали, что программа работоспособна:)

Единственный комментарий,

Единственный комментарий, который мне понадобился для понимания этой программы - это комментарий на 47 строке //читаем слово :-D

Илье, по коду (А вообще, это

Илье, по коду (А вообще, это должны бы делать Ваши одногрупники!):
1. Cтрока 20 - не работает, если s пусто; Нужна коррекция обработки пустого слова.
2. Хорошо бы уточнить на БНФ какой язык обрабатывается;
3. Cравните с распознавателем (функцией ) приведённым Наташей С. (и упрощённым мной)
4. Поскольку данное решение, в отличие от выше упомянутого, претендует на общность, следует привести структуру процедуры q для общего случая (в ней должны быть case-операторы как по состояниям, так и по символам)
5. Ну, явный перебор с отступами!!! На каждый отступ можно рекомендавать не более 3-4 позиций. И уж точно, нельзя допускать появления горизонтального скроллинга в стандартном окне отображения кода!

Наташа, не понял Вашей

Наташа, не понял Вашей реплики. Мне то кажется, что для
Вас принципиально новым элементом должна бы являться рекурсия.

Я намекала на то, что

Я намекала на то, что комментариев слишком много. Они мешают восприятию программы в целом.
Ну а рекурсию я пока понимаю интуитивно. Внутри подпрограммы запускаем ее же, внутри нее опять ее же и т.д. В итоге самая последняя из них присвоит ans окончательное true или false. И так по цепочке все завершатся. Я правильно понимаю?

С рекурсией - почти

С рекурсией - почти правильно. Ну, а если очень много или полное отсутствие комментариев - крайности, то я никак не на стороне приверженцев второй из них, коих 99%, включая и Вас (кстати, и это тоже входит в понятие СТИЛЬ).

И ещё. Илья писал свой текст

И ещё. Илья писал свой текст для людей , с уважением к ним и очень старался, чтобы им было комфортно в него вникать (даже не поленился разобраться в технике визуализации программных элементов и всё заново переписать, чтобы включить её возможности).
Но, увы, оказался редким (и даже неявно осуждаемым) исключением среди тех, кто тоже ждёт публичного участия, но при этом, в своём наспех набросанном, аморфном, никак не комментированном и неряшливом тексте, который, по мнению автора, "cойдёт и так".
О "присутствующих" не говорят :)).

Я ничего не имею против Ильи

Я ничего не имею против Ильи и комментариев! Увы я не могу посредством текста передавать интонацию, поэтому моя фраза, возможно, звучит слишком жестко.