Построение конечного автомата

[Ludmila]

Помогите пожалуйста построить конечный автомат для перевода дробных двоичныхчисел в десятичные

[Finch]

Ну вообше то я вижу простую арифметику. Убрать целую часть и пошел умножать на десять, пока не исчезнит дробная часть. Если сюда всовывать конечный автомат, то в приципе овчинка выделки не стоит.

[Вад]

Finch, ну задача-то, как я понимаю, учебная Хотя, может, автор опровергнет.

Ludmila, уточни, с чем конкретно проблема. Какие свои мысли есть? Не может быть, чтоб совсем не было

[Ludmila]

Так звучит моя курсовая работа по дискретной математике.Нужно расписать все состояния автомата что поступает на вход а что поступает на выход. что-то вроде такого (для перевода из двоичных в десятичный):
Например:
поступает двоичное число 001001
1) левые нули отбрасываются ;
2) w=1;
3) если 0, то w*2=2;
4) если 1, то w*2+1;
Конечно это всё нужно рассписать в виде таблицы и для перевода дробных двоичных чисел. А вот это я как раз и не знаю, практики было очень мало

[Ludmila]

Ну чего мне теперь делать если я реально не могу понять как построить конечный автомат? Ну  я не очень умная! Да я это признаю!Поэтому я к Вам и обратилась за помощью! Может я не понимаю даже элементарного! Я надеюсь на Вашу помощь, хотя б какую нибудь подсказочку!!!

[McZim]

Ludmila, как на счет научиться пользоваться поиском?

https://forum.shelek.ru/index.php/topic,4745.0.html

[Алексей++]

Ludmila, вот ешшо есть про автоматы
http://ru.wikipedia.org/wiki/%D0%9A%D0%BE%D0%BD%D0%B5%D1%87%D0%BD%D1%8B%D0%B9_%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82

[Ludmila]

Я не могу расписать состояния

[Ludmila]

Всё это я не раз просмотрела!Но понять как расписать я не могу

[Dr.Yevhenius]

Для начала ты должна выяснить, какие сигналы автомат принимает (все возможные)!

[Ludmila]

Впринципе это двоичный код значит 0 и 1 а если дрбные то значит ещё надо учесть запятую

[Dr.Yevhenius]

Теперь создай все необходимые переменные для реализации автомата (например - начало числа (отсечение нолей)). Если потом не будет хватать, то добавить можно в любую минуту...

[Dr.Yevhenius]

поступает двоичное число 001001
1) левые нули отбрасываются ;
2) w=1;
3) если 0, то w*2=2;
4) если 1, то w*2+1;

Перед тем как продолжать, уточни, что такое w?

[Вад]

Ludmila, как выглядит двоичное представление вещественного числа? Понятия экспоненты и мантиссы знакомы?

[Ludmila]

w - какая-либо переменная, от которой будет зависеть запись на выходе

[Вад]

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

Если под двоичными дробными понимается что-то совсем своё - то состояния будут несколько иными.

[Вад]

Ludmila, приводимый пример преподаватель дал?

[Ludmila]

Да

[Вад]

Тогда повторю вопрос:

Ludmila, как выглядит двоичное представление вещественного числа? Понятия экспоненты и мантиссы знакомы?

Потому что от этого зависит, какие будут состояния. Лучше представление числа изобразить схематически.

[Dr.Yevhenius]

Какие примеры у тебя есть - покажи их...

[Ludmila]

как какие Вот только то, что приведено выше и не более того

[Dr.Yevhenius]

(Я нашёл только 001001, если я не прав, скажите) Для 001001 тогда будет всего 3 сигнала - "0", "1" и "." (завершение введения), так это очень просто как для курсовой работы

[Ludmila]

а у меня тогда будет 4 сигнала "0" "1" "," "."?

[Dr.Yevhenius]

Понятия экспоненты и мантиссы знакомы?

Первый раз про мантиссы слышу... Зашёл на Википедию, прочитал, разобрался.
А теперь извините, не понял: зачем для 011001010 мантиссы и экспоненты, если такое двоичное представление можно сразу переводить в число?

(изменение: ну хотя бы число 100100111,100101?)

[Dr.Yevhenius]

У меня при создании автомата был такой алгоритм:
1) определение входных сигналов;
2) создание переменных;
3) создание графа переходов (+ досоздание переменных);
4) рисовал таблицу переходов;
5) и потом писал код программы.

[Вад]

Inkognito, поскольку я до сих пор не понял, какую запись дробного двоичного подразумевает задание, запись вида "100100111,100101" мне кажется сомнительной - никогда не видел, чтобы так записывали, даже для учебного задания.

[Dr.Yevhenius]

Вад, мне самому эта запись не нравится.

[Алексей++]

тоже никогда ещё не встречал применения дробного двоичного числа ))

[Ludmila]

Как вы считаете это правильно или бред?
Граф

[Ludmila]

где s1 s2 s3 s4 s5 состояния
s0 начальное состояние

[Dr.Yevhenius]

Для S0 не предусмотрены состояния "," и ".".
Для состояния S3 будет забрано только одну цифру, а все остальные проигнорируются.

И вообще не понятно, что будет делать данный автомат - как будут изменятся переменные: куда считываешь число до запятой и когда прекращаешь это делать и т. д. ... Это всё нужно показывать, мы на СР вообще так делали.

Кстати, должен быть ещё один тип сигнала - "Other" - все остальные символы.

[Ludmila]

да до всех символов дойти надо мне хотяб так пока

[Dr.Yevhenius]

да до всех символов дойти надо мне хотяб так пока

Все символы как раз обрабатывать и не надо, а игнорировать, это просто надо предусмотреть для каждого состояния и не более.

[Ludmila]

как вообще тогда перевести  дробное двоичное число в десятичное? Обычным способом? Но чего получится?

[Dr.Yevhenius]

Возьмём для начала состояние S0 (начальное). Если сигнал "." - прекратить работу автомата (перейти, например, к состоянию 1); если "0" - отсекаем ноль; если "1" - то в соответствии - число перед запятой или после - переходим к состоянию 2 или 3; если "Other" (остальные символы) - нечего не делать; если "," - перейти, например, к состоянию 3... И так для каждого состояния описываешь все варианты. А при выходе обработать данные.

Кстати, как добавить рисунок в сообщение? А, всё, нашёл.

[Ludmila]

а как тогда на выходе обработать данные?

[Dr.Yevhenius]

Я сделал бы функцию превращения двоичного числа в десятичное - 1111 в 15.

[Ludmila]

?а если число 10,1 то как по обычному 10,1=1*2^1+0*2^0+1*2^(-1) так?

[Ludmila]

как? какая функция?

[Dr.Yevhenius]

Хотя 10,1 вероятней всего неверный способ, но я сделал бы так: 10 = 2, 1 = 1, а тогда результат равен 2,1.

[Ludmila]

это как так? на по всем правилам перевода 10,1=2,5?

[Dr.Yevhenius]

как? какая функция?

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

Я не понимаю вопроса...

[Алексей++]

1*2¹+0*2⁰+1*2^-1 = 2 + 0 + 0.5 = 2.5  , всё верно девушка говорит

[Ludmila]

Хотя 10,1 вероятней всего неверный способ, но я сделал бы так: 10 = 2, 1 = 1, а тогда результат равен 2,1.

да да Алексей1153 правильно говорит как у тебя 2,1 получилась?

[Dr.Yevhenius]

1*2¹+0*2⁰+1*2^-1 = 2 + 0 + 0.5 = 2.5  , всё верно девушка говорит

Вообще-то да, согласен, не понял, извините...

[Ludmila]

ну так  кто знает как на выходе обработать данные?

[Dr.Yevhenius]

Хотя с другой стороны вот сравнения:
1) моим способом:
10,1 - 2,1
10,10 - 2,2
10,11 - 2,3
2) вашим способом:
10,1 - 2,5
10,10 - 2,5
10,11 - 2,75.

[Алексей++]

наверное, надо накапливать результат в переменной

[Алексей++]

Хотя с другой стороны вот сравнения:
1) моим способом:
10,1 - 2,1
10,10 - 2,2
10,11 - 2,3
2) вашим способом:
10,1 - 2,5
10,10 - 2,5
10,11 - 2,75.

2 - верно )

[Ludmila]

( я тоже за (2)

[Dr.Yevhenius]

Я в Инете нашёл вот такое представление числа с запятой:
aaaabbbb,
и тогда получаем число через экспоненту и мантиссу в виде:
aaaa*2^bbbb.

[Ludmila]

вот предыдущий мой пример:
                   1001
w=1;<-------| | | |
w*2=2;<-----| | |
w*2=4;<-------| |
w*2+1=9.<------|
Это ж вроде верно

[Dr.Yevhenius]

1001₂ = 9₁₀ это верно

[Алексей++]

Inkognito, это вообще то не метод, а правило

[Ludmila]

а вот дробную часть далше как превратить

[Алексей++]

первое число после запятой умножается на основание в -1 степени, второе - в -2 степени и так далее

[Ludmila]

стоп стоп стоп вот выходы:
b1=левые нули "выбывают" до тех пор пока входной символ небует равен x=1
b2=если x0 = 1, то w: = 1
b3=если х1 = 0, то w*2
b4=если x1 = 1, то w*2+1
b5=если  "," ?
b6=если x2 = 0 ?
b7= если х2= 1 ?

[Dr.Yevhenius]

Вот мой вариант графа:

[Ludmila]

0 1 2 3 - это состояния значит?

[Dr.Yevhenius]

Да, состояния

[Ludmila]

Спасибочки!Надо ещё подробней разобраться)
А обработку как вообще делать?

[Dr.Yevhenius]

Перевести двоичные числа ch1 и ch2 в десятичные, ch1 переводить с повышением степеня (1*2⁰ + 0*2¹ + 1*2²...), а ch2 - с его понижением (0*2^-1 + 1*2^-2...). Потом сложить эти два результата и получим окончательный результат, который можно выводить на экран. Именно это я имел ввиду под словом "обработка". Но это в том случае, если делать за моим графом. Если у тебя другой граф, то обработку нужно делать соответственно до твоей постановки решения. 

[Ludmila]

То есть обработка данных- это сложить?

[Алексей++]

Inkognito, Ludmila, не совсем так получается: строку то рассматриваем слева направо, поэтому

до точки:

                 результат =
первый символ|   A_n
второй символ|   *2 + A_n-1
третий символ|   *2 + A_n-2
...............|
последний     |   *2 + A₁


после точки:

                 результат = результат +
первый символ|   B₁ /2
второй символ|  +B₂ /4
третий символ|  +B₃ /8
...............|
последний     |  +B_m /2^-m

[Dr.Yevhenius]

Inkognito, Ludmila, не совсем так получается: строку то рассматриваем слева направо, поэтому

ch1 и ch2 - строчки. ch2 - рассматриваем слева направо, а ch1 - справа налево, иначе да результат будет неправильным

[Dr.Yevhenius]

То есть обработка данных- это сложить?

Если ты сложишь ch1 и ch2, то получишь число в двоичной системе; сложить надо уже в конце два десятичных числа...

Давай по-порядку. Первое это

Перевести двоичные числа ch1 и ch2 в десятичные

На каком языке программирования ты будеш делать код?? Для начала сделай функцию перевода двоичного числа в десятичное: принимает 1111 и возвращает 15.

[Ludmila]

Буду делать скорее всего на СИ

[Алексей++]

тогда, насколько я понимаю, автомата не выйдет. Надо всё слева направо

[Ludmila]

Да и автомат можно и не программирывать! просто таблицы составить алгоритм ! А на каком можно сделать автомат Паскаль?

[Dr.Yevhenius]

тогда, насколько я понимаю, автомата не выйдет. Надо всё слева направо

Автомат будет забирать сигналы слева направо. А работа с числом ch1 будет идти справа налево КОГДА автомат уже и так примет сигнал остановки и работать не должен.

Граф - это только рисунок, чтобы было легче делать алгоритм...

[Ludmila]

Так на каком языке можно сделать автомат?

[RXL]

Так на каком языке можно сделать автомат?

На любом - ограничений для этого нет. Какие языки ты знаешь?

[Dr.Yevhenius]

Так на каком языке можно сделать автомат?

На любом, даже на JavaScript.

Главное знать этот язык, на котором будешь делать работу...(не заметил ответа  )

[Ludmila]

JavaScript капельку знаю Assembler C Paskal HTML CSS Visual Basic тока начала

[Ludmila]

Правда это всё не в совершенстве (Assembler C Paskal)

[Dr.Yevhenius]

В совершенстве знать и не надо. Хватит знаний основных типов данных, операторов сравнения, циклов и переключателей.

[Ludmila]

но на Си всё таки мне ближе

ГЛАВНОЕ ДЛЯ МЕНЯ РАСПИАТЬ ВСЕ СОСТОЯНИЯ ТАБЛИЦУ ПЕРЕХОДОВ И ТО ЧТО ПОЛУЧИТСЯ НА ВЫХОДЕ
А самое самое важное понять весь этот принцип и защититься

Вот я ещё не совсем поняла Получается мой автомат будет задан такими параметрами M=(N(Конечное множество состояний автомата),n0(начальноу состояние)S(входной алфавит),B(выходной алфавит))
Так?
И вот ещё как понять допускающее и недопускающее состояние?
У меня такое будет?

[Finch]

Ну конечные автоматы еше называют switch технология.
Строится примерно так

Код:

int stat=1;
while (stat)
{
   switch(stat)
   {
       case 1:
           //Тут действия для 1 состояния 
           break;
       case 2:
           //Тут действия для 2 состояния 
           break;
       case 3:
           //Тут действия для 3 состояния 
           break;
       case 4:
           //Тут действия для 4 состояния 
           break;
      .............
   }
}

состояние 0 будет выходом из автомата.

[Ludmila]

)Да прошло конечно очень много дней, с тех пор как я здесь появлялась!)Извеняюсь что так долго не заходила!Но могу сказать что эту курсовую я защитила на отлично!Я Вас всех благодарю, ведь только Вы поддержали меня в столь трудную тогда для меня минуту!