Разработка методологии исследования для курсовой работы: Программа перевода чисел, написанных прописью, в числовой формат с использованием теории автоматов

В эпоху цифровизации, когда взаимодействие человека с машиной становится всё более естественным, задача обработки естественного языка приобретает особую актуальность. Одним из таких направлений является автоматизированный перевод числительных, написанных прописью, в числовой формат. Это не просто академический интерес, но и практическая необходимость во многих областях: от систем распознавания речи и голосовых помощников до финансового программного обеспечения и обработки документов. Представьте себе ситуацию, когда необходимо мгновенно конвертировать «двадцать пять тысяч триста сорок семь» в 25347, избегая человеческих ошибок и ускоряя процессы. Именно на решение этой задачи направлена данная курсовая работа.

Цель настоящего исследования — разработать и обосновать методологию создания программы, способной осуществлять точный и эффективный перевод русских числительных, записанных прописью, в их числовое представление в диапазоне от -10000 до 10000. В качестве фундаментальной основы для решения этой задачи выбрана теория автоматов, а именно детерминированные конечные автоматы (ДКА), что позволяет применить строгий формальный аппарат для лексического анализа.

В рамках работы будут последовательно рассмотрены теоретические основы лексического анализа и ДКА, детально описан процесс проектирования ДКА, представлены алгоритмы преобразования текстовых числительных в числа, изложены особенности программной реализации на языке C#, а также предложены методы тестирования и валидации разработанного продукта. Завершит исследование анализ возможностей по дальнейшему расширению функциональности программы.

Теоретические основы лексического анализа и детерминированных конечных автоматов

В основе любой системы, обрабатывающей текстовые данные, лежит фундаментальный процесс, который в компьютерных науках известен как лексический анализ. Он представляет собой своеобразный «первый контакт» программы с человеческим языком, позволяющий машине начать понимать смысл в потоке символов, преобразуя их в структурированные данные. Важно понимать, что без этого шага дальнейшая обработка, например, синтаксический или семантический анализ, была бы невозможна.

Понятие лексического анализа и его роль

Лексический анализ, или токенизация, — это краеугольный камень в архитектуре компиляторов, интерпретаторов и других систем обработки текста. Его суть заключается в разбиении входящей последовательности символов на значимые, неделимые единицы, называемые лексемами. Представьте, что вы читаете книгу: вы не воспринимаете текст как хаотичный набор букв, а как слова и предложения. Лексический анализатор делает то же самое для компьютера.

Каждая лексема — это конкретная последовательность символов, например, «сто», «минус», «двадцать». Эти лексемы, в свою очередь, преобразуются в токены. Токен — это уже не просто строка символов, а абстрактный символ, который несёт в себе информацию о типе лексемы и её атрибутах. Например, лексема «сто» может стать токеном `(Числительное, значение: 100)`, а «минус» — `(Знак, значение: -1)`. Токены являются строительными блоками для последующего синтаксического анализа.

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

Детерминированные конечные автоматы (ДКА)

В мире информатики существует множество абстрактных моделей, помогающих нам понять и решить сложные задачи. Одной из наиболее элегантных и мощных является Детерминированный Конечный Автомат (ДКА). Это математическая модель, способная «читать» входную строку символов и, основываясь на определённых правилах, принимать или отклонять её.

Формально, ДКА определяется как кортеж M = (Q, Σ, δ, q₀, F), где:

• Q — это конечное множество состояний, в которых может находиться автомат. Каждое состояние отражает определённый этап обработки входной последовательности.
• Σ — это конечный входной алфавит, то есть набор всех возможных символов, которые может прочитать автомат.
• δ (дельта) — это функция переходов, которая определяет, в какое следующее состояние перейдёт автомат из текущего, прочитав определённый символ. Её можно представить как Q × Σ → Q.
• q₀ — это начальное состояние, с которого всегда начинается работа автомата.
• F — это множество заключительных (или принимающих) состояний. Если по окончании обработки всей входной строки автомат находится в одном из этих состояний, то строка считается распознанной (принятой).

Принцип работы ДКА прост: начиная с q₀, автомат последовательно читает символы входной строки. Для каждого символа, используя функцию переходов δ, он определяет следующее состояние. Поскольку автомат детерминирован, для каждой пары (состояние, входной символ) существует только один возможный переход. Если после обработки всех символов автомат оказывается в состоянии из множества F, входная строка успешно распознана.

Примеры применения ДКА:

Помимо их классического использования в компиляторах и тестировании программного обеспечения, ДКА нашли широкое применение в самых разнообразных областях:

• Распознавание символов: ДКА идеально подходят для идентификации действительных чисел, ключевых слов в языках программирования, электронных адресов, URL-адресов и других структурированных текстовых паттернов.
• Анализ и обработка текста: От подсветки синтаксиса в текстовых редакторах до проверки орфографии, поиска и замены текста — везде можно найти применение ДКА.
• Управление процессами: В промышленных системах управления двигателем, сетевых протоколах (например, TCP/IP), робототехнике, ДКА используются для моделирования и управления последовательностями событий.
• Проектирование цифровых схем: Счетчики, таймеры, регистры и другие логические элементы цифровой электроники могут быть описаны и спроектированы с использованием конечных автоматов.
• Алгоритмы для поиска в строках, сжатия данных, шифрования: Многие алгоритмы, требующие последовательной обработки данных с изменением состояния, опираются на принципы конечных автоматов.

Регулярные выражения и их связь с ДКА

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

Суть их связи с ДКА кроется в глубокой математической эквивалентности: любой язык, который может быть описан регулярным выражением, может быть распознан детерминированным конечным автоматом, и наоборот. Это означает, что для каждого регулярного выражения можно построить эквивалентный ДКА, который будет принимать те же строки, что и описывает регулярное выражение. Эта фундаментальная теорема является основой для автоматического построения лексических анализаторов, где сначала определяются шаблоны токенов в виде регулярных выражений, а затем эти выражения преобразуются в конечные автоматы.

Авторитетные источники по теории автоматов

Для глубокого понимания и корректной реализации принципов теории автоматов и лексического анализа, необходимо опираться на проверенные академические источники. В этой области существуют настоящие «киты», чьи труды стали классикой:

• Ахо, Ульман, Сети (Aho, Ullman, Sethi), «Компиляторы: принципы, технологии и инструменты»: Этот учебник, часто называемый «Книгой Дракона» (из-за изображения дракона на обложке), является золотым стандартом в области компиляторостроения. Первое издание на английском языке вышло в 1986 году, второе — в 2006 году, а русскоязычное издание второго издания — в 2008 году. В нём подробно изложены все этапы создания компилятора, начиная с лексического анализа и заканчивая генерацией кода, с глубоким погружением в теорию автоматов.
• Карпов Ю.Г., «Теория автоматов»: Монография Ю.Г. Карпова, изданная в 2003 году, является авторитетным русскоязычным источником, предлагающим систематическое изложение теории конечных автоматов, включая их математический аппарат, алгоритмы построения и применения.

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

Проектирование ДКА для распознавания русских числительных (-10000 до 10000)

Проектирование детерминированного конечного автомата (ДКА) для распознавания числительных — это задача, требующая не только понимания теории автоматов, но и глубокого знания специфики русского языка. В данном разделе мы погрузимся в детали создания такого автомата, ориентированного на диапазон чисел от -10000 до 10000.

Применимость ДКА для анализа числительных

Почему именно ДКА так хорошо подходит для задачи распознавания числительных? Ответ кроется в формальных языках. Языки констант и идентификаторов, к которым относятся и числительные, являются так называемыми регулярными языками. Это означает, что их синтаксис может быть описан с помощью регулярных грамматик, а регулярные грамматики, в свою очередь, могут быть эффективно распознаны конечными автоматами, в частности, ДКА.

Регулярность языка числительных позволяет нам построить конечный автомат, который, перемещаясь от одного состояния к другому в зависимости от прочитанного слова-числительного, однозначно определит, является ли входная последовательность корректным числом, записанным прописью, и какое именно значение оно представляет.

Особенности грамматической структуры русских числительных

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

Основные особенности, которые необходимо учесть при проектировании ДКА:

• Согласование по роду: Числительные «один» и «два» имеют разные формы в зависимости от рода существительного, с которым они согласуются: «один» (муж. род), «одна» (жен. род), «одно» (ср. род); «два» (муж. и ср. род), «две» (жен. род). Хотя в нашей задаче мы переводим в число, а не согласуем с существительными, ДКА должен быть готов к распознаванию всех этих форм.
• Особые формы десятков: Числа «сорок» и «девяносто» отличаются от общего принципа образования десятков (например, «двадцать», «тридцать»), имея уникальные формы, не образующиеся путём добавления суффиксов.
• Склонение сотен: Сотни также имеют специфические правила образования и склонения (например, «сто», «двести», «триста», «четыреста», «пятьсот», «шестьсот», «семьсот», «восемьсот», «девятьсот»). ДКА должен уметь распознавать эти формы и правильно агрегировать их значения.
• Склонение «тысяча»: Слово «тысяча» ведет себя как существительное женского рода, имея формы «тысяча», «тысячи», «тысяч» в зависимости от предшествующего числительного (например, «одна тысяча», «две тысячи», «пять тысяч»).
• Составные числительные: Образование чисел, таких как «двадцать пять», «триста сорок два», «пять тысяч сто тридцать семь», требует последовательного распознавания и агрегации значений.

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

Определение лексических единиц для диапазона (-10000 до 10000)

Для успешного проектирования ДКА, прежде всего, необходимо составить полный список всех лексических единиц — слов-числительных, которые автомат должен уметь распознавать в заданном диапазоне от -10000 до 10000. Этот диапазон включает как положительные, так и отрицательные числа, а также ноль.

Перечень ключевых лексических единиц:

• Знак: «минус»
• Ноль: «ноль»
• Единицы (1-9): «один», «одна», «одно», «два», «две», «три», «четыре», «пять», «шесть», «семь», «восемь», «девять»
• Числа от 10 до 19: «десять», «одиннадцать», «двенадцать», «тринадцать», «четырнадцать», «пятнадцать», «шестнадцать», «семнадцать», «восемнадцать», «девятнадцать»
• Десятки (20-90): «двадцать», «тридцать», «сорок», «пятьдесят», «шестьдесят», «семьдесят», «восемьдесят», «девяносто»
• Сотни (100-900): «сто», «двести», «триста», «четыреста», «пятьсот», «шестьсот», «семьсот», «восемьсот», «девятьсот»
• Тысячи (1000-10000): «тысяча», «тысячи», «тысяч», «десять тысяч»

Каждое из этих слов будет представлять собой входной символ для нашего ДКА, по которому будут осуществляться переходы между состояниями.

Структура состояний и переходов ДКА

Проектирование ДКА начинается с определения набора состояний, которые будут отражать прогресс в распознавании числового выражения. Затем прорабатываются правила переходов между этими состояниями.

Предлагаемая схема состояний для нашего ДКА:

1. Начальное состояние (Start):
   • Это отправная точка. Автомат ожидает первое слово.
   • Возможные переходы:
     • По слову «минус» → Состояние «Минус».
     • По любому числительному (от «ноль» до «девятьсот», а также «тысяча») → соответствующее состояние (например, Состояние Единиц, Состояние Десятков, Состояние Сотен, Состояние Тысяч).
2. Состояние «Минус» (Negative):
   • Достигается после распознавания слова «минус».
   • Ожидается положительное числительное.
   • Переходы: По любому положительному числительному → соответствующее состояние (например, Состояние Единиц), с флагом отрицательного числа.
3. Состояние Единиц (Units):
   • Достигается после распознавания числительных от «один» до «девятнадцать» (или их родовых форм).
   • Может быть конечным для простых чисел.
   • Возможные переходы:
     • По «тысяча»/»тысячи»/»тысяч» → Состояние Тысяч.
     • Достижение конца строки → Конечное состояние.
4. Состояние Десятков (Tens):
   • Достигается после распознавания числительных «двадцать», «тридцать», …, «девяносто», а также «десять», «одиннадцать», …, «девятнадцать».
   • Возможные переходы:
     • После «двадцать», «тридцать», …, «девяносто» ожидается единица (например, «двадцать пять») → Состояние Единиц.
     • По «сто», «двести» и т.д. (для случаев вроде «сто двадцать пять») → Состояние Сотен.
     • По «тысяча»/»тысячи»/»тысяч» → Состояние Тысяч.
     • Достижение конца строки → Конечное состояние.
5. Состояние Сотен (Hundreds):
   • Достигается после распознавания «сто», «двести», …, «девятьсот».
   • Возможные переходы:
     • По единицам или десяткам (для составных чисел, например, «двести тридцать») → Состояние Единиц/Десятков.
     • По «тысяча»/»тысячи»/»тысяч» → Состояние Тысяч.
     • Достижение конца строки → Конечное состояние.
6. Состояние Тысяч (Thousands):
   • Достигается после распознавания «тысяча», «тысячи», «тысяч».
   • В этом состоянии происходит умножение текущей накопленной суммы на 1000.
   • Ожидается следующая группа чисел (сотни, десятки, единицы).
   • Возможные переходы:
     • По числительным «сто», «двести» и т.д. → Состояние Сотен.
     • По числительным «двадцать», «тридцать» и т.д. → Состояние Десятков.
     • По числительным «один», «два» и т.д. → Состояние Единиц.
     • Достижение конца строки → Конечное состояние.
7. Конечное состояние (Final):
   • Достигается после успешного распознавания полного числового выражения.

Пример логики переходов:

• Вход: «сто двадцать пять»
  • Start → «сто» → Состояние Сотен (накоплено 100)
  • Состояние Сотен → «двадцать» → Состояние Десятков (накоплено 100 + 20)
  • Состояние Десятков → «пять» → Состояние Единиц (накоплено 100 + 20 + 5 = 125)
  • Состояние Единиц → конец строки → Конечное состояние (результат: 125)
• Вход: «две тысячи триста»
  • Start → «две» → Состояние Единиц (накоплено 2)
  • Состояние Единиц → «тысячи» → Состояние Тысяч (накоплено: 2 * 1000 = 2000)
  • Состояние Тысяч → «триста» → Состояние Сотен (накоплено: 2000 + 300 = 2300)
  • Сос��ояние Сотен → конец строки → Конечное состояние (результат: 2300)

Семантические действия для накопления числового значения

Сами по себе переходы между состояниями ДКА только подтверждают корректность синтаксиса. Для получения числового значения необходимы семантические действия, привязанные к этим переходам или к достижению определённых состояний. Эти действия позволяют постепенно накапливать и агрегировать числовое значение.

Примеры семантических действий:

• Начальная инициализация: Перед началом работы автомата инициализируются переменные: currentValue = 0 (для текущего разряда, например, единиц, десятков, сотен) и totalValue = 0 (для тысяч и общего итога), а также sign = 1 (для знака числа).
• Обработка «минус»: При переходе из Start в Состояние «Минус» по слову «минус», устанавливается sign = -1.
• Обработка единиц, десятков, сотен: Когда автомат распознаёт слова, соответствующие единицам (1-9), десяткам (10-90) или сотням (100-900), их числовые значения добавляются к currentValue.
  • Например, если распознано «двести», currentValue становится 200. Если затем распознано «тридцать», currentValue становится 230. Если затем «пять», currentValue становится 235.
• Обработка тысяч: При переходе в Состояние Тысяч (по словам «тысяча», «тысячи», «тысяч»):
  • Значение currentValue умножается на 1000 и добавляется к totalValue.
  • currentValue сбрасывается в 0, чтобы начать накопление следующей группы чисел (сотни, десятки, единицы после тысяч).
  • Например, если currentValue было 2 (от «две») и распознано «тысячи», то totalValue += 2 * 1000 = 2000. currentValue обнуляется. Далее, если распознано «триста», currentValue становится 300.
• Окончательное формирование числа: По достижении Конечного состояния, окончательный результат вычисляется как (totalValue + currentValue) * sign.

Такой подход позволяет эффективно обрабатывать составные числительные, корректно учитывая разрядность и знак числа.

Алгоритмы лексического анализа и преобразования слов в числа

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

Построение лексического анализатора на основе ДКА

Создание лексического анализатора — это процесс, который традиционно начинается с описания синтаксиса лексем с помощью регулярных выражений. Затем эти регулярные выражения преобразуются в конечные автоматы.

Последовательность шагов обычно такова:

1. Регулярное выражение в Недетерминированный Конечный Автомат (НКА):
   • На первом этапе каждое регулярное выражение, описывающее шаблон токена (например, для «сто», «минус», «тысяча»), преобразуется в эквивалентный НКА.
   • Наиболее распространенным алгоритмом для этой цели является алгоритм Томпсона. Он позволяет систематически строить НКА для любых регулярных выражений, начиная с базовых операций (конкатенация, объединение, итерация Клини). Особенность НКА в том, что из одного состояния по одному и тому же входному символу может быть несколько переходов, или переходы по «ε» (пустой строке).
2. НКА в Детерминированный Конечный Автомат (ДКА):
   • Хотя НКА проще строить, ДКА более эффективны для исполнения. Поэтому следующим шагом является преобразование построенного НКА в эквивалентный ДКА.
   • Для этого используется метод подмножеств (subset construction). Этот алгоритм позволяет устранить недетерминированность, создавая новые состояния в ДКА, которые представляют собой множества состояний НКА. Каждое такое множество соответствует всем возможным состояниям, в которых НКА мог бы находиться после обработки определённой входной последовательности.
   • Конечный ДКА, построенный таким образом, будет принимать ровно те же строки, что и исходный НКА, и, следовательно, те же, что описывались исходным регулярным выражением.

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

Этапы работы лексического анализатора

После того как ДКА построен (или определён), лексический анализатор приступает к своей непосредственной работе:

1. Чтение входной строки: Анализатор начинает читать входной текст, содержащий числительные, написанные прописью.
2. Разбиение на потенциальные лексемы: В случае с числительными, написанными прописью, это может быть разбиение по пробелам, чтобы получить отдельные слова (например, «двадцать», «пять», «тысяч»).
3. Идентификация и классификация лексем: Для каждого слова лексический анализатор использует свой внутренний ДКА (или таблицу переходов, построенную на основе ДКА), чтобы определить, к какому типу токенов оно относится (например, «числительное-единица», «числительное-десяток», «числительное-тысяча», «знак»). Если слово не соответствует ни одному из шаблонов, это сигнализирует об ошибке.
4. Формирование токенов: После идентификации лексемы создаётся токен, который содержит информацию о типе лексемы и её атрибутивном значении (например, для «сто» это может быть токен (NUM, 100)).
5. Передача потока токенов: Сформированный поток токенов передаётся следующему этапу обработки — парсеру, который будет заниматься уже семантическим анализом и преобразованием.

Алгоритм преобразования токенов-числительных в число

Этот алгоритм, по сути, является набором семантических действий, которые мы ранее кратко рассмотрели. Он принимает на вход поток токенов от лексического анализатора и последовательно агрегирует их значения для получения окончательного числового результата.

Детализированный алгоритм:

1. Инициализация:
   • result = 0 (итоговое числовое значение)
   • current_group_value = 0 (накопитель для текущей группы разрядов: единиц, десятков, сотен)
   • multiplier_for_thousands = 1 (множитель для учета тысяч, по умолчанию 1)
   • is_negative = false (флаг для отрицательных чисел)
2. Итерация по токенам:
   • Если токен «минус»:
     • is_negative = true
   • Если токен представляет собой числовую единицу (1-9), десяток (20-90), или число от 10 до 19, или сотню (100-900):
     • Добавить числовое значение токена к current_group_value.
   • Если токен «тысяча», «тысячи», «тысяч»:
     • result += current_group_value * 1000
     • current_group_value = 0 (сбросить для следующей группы чисел)
     • Примечание: Это упрощённый подход. В более сложном случае, когда число превышает 10000, multiplier_for_thousands может быть 1000, затем 1000000 и т.д., и result будет накапливать значения групп, умноженные на соответствующий множитель. Для диапазона до 10000 это достаточно.
   • Особый случай «десять тысяч»: Если распознается «десять тысяч», то можно напрямую добавить 10000 к result (или current_group_value и затем обработать как thousands).
3. Завершение:
   • После обработки всех токенов, оставшееся значение current_group_value (если оно не было обнулено «тысячами») добавляется к result.
   • result += current_group_value
   • Если is_negative истинно, то result = result * (-1).

Этот алгоритм позволяет корректно обрабатывать составные числительные, где сначала накапливаются значения в пределах сотен, затем умножаются на 1000, и снова начинается накопление сотен, десятков и единиц.

Например, для «две тысячи триста двадцать пять»:

1. «две» → current_group_value = 2
2. «тысячи» → result = 2 * 1000 = 2000, current_group_value = 0
3. «триста» → current_group_value = 300
4. «двадцать» → current_group_value = 300 + 20 = 320
5. «пять» → current_group_value = 320 + 5 = 325
6. Конец → result += 325. Итого: 2000 + 325 = 2325.

Этот подход обеспечивает гибкость и точность в преобразовании прописных числительных в их числовой эквивалент.

Особенности программной реализации на C#

Язык C# и платформа .NET предлагают мощные средства для реализации сложных алгоритмов, в том числе и для работы с теорией автоматов. Проектирование программного продукта на C# требует структурированного подхода, использования объектно-ориентированных принципов и эффективной обработки потенциальных ошибок.

Моделирование ДКА в C#

Для моделирования ДКА в C# можно использовать объектно-ориентированный подход, где каждое состояние и сам автомат представлены классами. Это обеспечивает модульность, читаемость и расширяемость кода.

Класс State (Состояние):
Этот класс будет представлять отдельное состояние в ДКА. Он должен хранить следующую информацию:

• Имя состояния (например, string Name): Для идентификации состояния.
• Признак заключительного состояния (bool IsFinal): Указывает, является ли это состояние принимающим.
• Список переходов (Dictionary<string, State> Transitions): Это ключевой элемент. Поскольку входными «символами» для нашего ДКА являются целые слова-числительные (строки), а не отдельные символы, Dictionary<string, State> идеально подходит. Ключом будет слово-числительное (например, «сто»), а значением — следующее состояние, в которое произойдёт переход.

Класс DFA (Детерминированный Конечный Автомат):
Этот класс будет управлять всеми состояниями автомата и логикой его выполнения.

• Начальное состояние (State InitialState): Ссылка на стартовое состояние.
• Множество всех состояний (List<State> AllStates или Dictionary<string, State> для быстрого доступа).
• Текущее состояние (State CurrentState): Переменная, отслеживающая, в каком состоянии находится автомат в данный момент.
• Метод ProcessInput(string word): Принимает слово-числительное, находит соответствующий переход из CurrentState и обновляет CurrentState. Если перехода нет, генерирует исключение или возвращает индикатор ошибки.
• Метод Reset(): Возвращает CurrentState в InitialState.

Таким образом, простейший интерпретатор конечного автомата на C# будет итерироваться по входным словам (которые уже были разбиты на лексемы) и, используя Transitions в текущем State, менять CurrentState.

Структура классов программного продукта

Для создания полноценного программного продукта, который будет не просто моделировать ДКА, но и выполнять весь процесс перевода чисел, рекомендуется следующая структура классов:

1. State и DFA (как описано выше): Эти классы формируют ядро механизма распознавания лексем.
2. Lexer (Лексический анализатор):
   • Отвечает за разбиение входной строки текста на отдельные слова-числительные (лексемы).
   • Может использовать внутренний DFA для классификации этих слов в токены (хотя для простых числительных можно обойтись словарями).
   • Возвращает поток (например, IEnumerable<Token>) или список List<Token> токенов.
   • Пример токена: { Type: "UNIT", Value: "пять", NumericValue: 5 }.
3. Token (Токен):
   • Простой класс или структура, хранящая тип токена (например, TokenType.Unit, TokenType.Ten, TokenType.Hundred, TokenType.Thousand, TokenType.Minus) и его строковое/числовое значение.
4. NumberParser (Парсер чисел):
   • Принимает поток Token от Lexer.
   • Реализует алгоритм преобразования токенов-числительных в число (тот самый алгоритм семантических действий, описанный ранее).
   • Возвращает конечный int или long результат.
   • Этот класс будет содержать основную логику накопления значений и обработки разрядов.

Эта структура обеспечивает чёткое разделение ответственности (Separation of Concerns): Lexer занимается разбором слов, DFA — их распознаванием, а NumberParser — семантическим преобразованием.

Обработка отрицательных чисел

Для корректной обработки отрицательных чисел можно использовать следующую логику в NumberParser:

• В NumberParser заводится булева переменная bool isNegative = false.
• Когда Lexer выдаёт токен, соответствующий слову «минус», NumberParser устанавливает isNegative = true.
• Все последующие числовые токены обрабатываются как положительные.
• В самом конце, после завершения парсинга всех числовых токенов и агрегации их значений, если isNegative равно true, итоговое число умножается на -1.

Пример: «минус двадцать пять»

1. Lexer выдаёт (MINUS, "минус"). NumberParser устанавливает isNegative = true.
2. Lexer выдаёт (TEN, "двадцать", 20). current_group_value = 20.
3. Lexer выдаёт (UNIT, "пять", 5). current_group_value = 25.
4. Конец входной строки. Итоговое накопленное значение 25.
5. Так как isNegative равно true, результат 25 * (-1) = -25.

Работа с исключениями и некорректным вводом

Надёжная программа должна уметь обрабатывать некорректный ввод. В C# для этого используется механизм исключений (try...catch...finally).

• try...catch: Блоки try охватывают код, который может вызвать исключение. Если исключение происходит, выполнение переходит в соответствующий блок catch, где можно обработать ошибку (например, вывести сообщение пользователю, записать в лог).
  • Например, если Lexer встречает слово, не являющееся числительным, он может сгенерировать FormatException или ArgumentException. NumberParser должен перехватить это исключение и сообщить о недействительном формате.
• Методы TryParse(): Для преобразования строк в числа (хотя в нашем случае мы уже работаем со словами-числительными, которые будут сопоставляться с заранее определёнными числовыми значениями) в .NET существуют методы TryParse() (например, int.TryParse()). Они предпочтительнее методов Parse(), поскольку Parse() генерирует исключение FormatException при некорректном формате, тогда как TryParse() просто возвращает false и не выбрасывает исключение, что позволяет писать более устойчивый код. В нашем контексте, TryParse может быть полезен, если мы захотим, например, попытаться преобразовать «5» в число, если это разрешено спецификацией.
• Создание пользовательских исключений: Для более специфических ошибок, таких как «Некорректная последовательность числительных» (например, «пять сто»), можно создать собственные классы исключений (например, InvalidNumberFormatException), наследующиеся от Exception.

public class InvalidNumberFormatException : Exception
{
    public InvalidNumberFormatException(string message) : base(message) { }
}

// Пример использования в NumberParser
try
{
    // ... логика парсинга
    if (/* некорректная последовательность слов */)
    {
        throw new InvalidNumberFormatException("Некорректная последовательность числительных.");
    }
}
catch (InvalidNumberFormatException ex)
{
    Console.WriteLine($"Ошибка при парсинге: {ex.Message}");
    // Дополнительная обработка
}
catch (Exception ex) // Для любых других непредвиденных ошибок
{
    Console.WriteLine($"Непредвиденная ошибка: {ex.Message}");
}

Выбор числового типа данных

Для хранения числового результата в диапазоне от -10000 до 10000 наиболее подходящим является тип int.

Обоснование:

• Диапазон: Тип int в C# обычно представляет собой 32-битное целое число со знаком, что обеспечивает диапазон значений от -2 147 483 648 до 2 147 483 647. Этот диапазон с большим запасом покрывает требуемый диапазон от -10000 до 10000.
• Эффективность: int является наиболее эффективным целочисленным типом для большинства процессоров и оптимально обрабатывается средой .NET, обеспечивая наилучшую производительность и минимальное использование памяти по сравнению с long (64-битное целое) или decimal (для финансовых расчётов с высокой точностью).
• Простота: Использование int упрощает код и избегает излишней сложности, которая могла бы возникнуть при работе с более крупными или точными типами данных, не являющимися необходимыми для данной задачи.

Если бы диапазон чисел был значительно больше (например, до миллиардов или триллионов), то стоило бы рассмотреть long. Для дробных чисел или высокоточных финансовых расчетов подошел бы decimal или double. Но для текущей задачи int — оптимальный выбор.

Методы тестирования и валидации программного продукта

Разработка программного обеспечения, каким бы тщательно спроектированным оно ни было, не может считаться завершённой без всестороннего тестирования. Цель тестирования — не просто убедиться, что программа работает, но и активно искать ошибки, которые могут привести к некорректному поведению. Валидация же подтверждает, что программа соответствует всем предъявляемым к ней требованиям.

Цели и виды тестирован��я

Цель тестирования: Главная цель тестирования — максимизация числа обнаруживаемых ошибок. Это означает не просто проверку «счастливых путей», но и активное исследование граничных условий, некорректных вводов и потенциальных уязвимостей.

Для программы перевода чисел прописью можно выделить следующие виды тестирования:

1. Модульное тестирование (Unit Testing):
   • Что проверяется: Отдельные, наименьшие компоненты программы, такие как отдельные функции, методы или классы.
   • Примеры для нашей задачи:
     • Функции распознавания отдельных слов-числительных (например, GetNumericValue("сто") должен вернуть 100).
     • Функции переходов состояний ДКА (например, из состояния Start по слову «минус» происходит переход в NegativeState).
     • Функции Lexer, отвечающие за разбиение строки на слова.
     • Методы NumberParser, отвечающие за агрегацию значений (например, AddUnit(5)).
   • Инструменты: NUnit, xUnit, MSTest в C#.
2. Интеграционное тестирование (Integration Testing):
   • Что проверяется: Взаимодействие между различными модулями (компонентами) системы.
   • Примеры для нашей задачи:
     • Проверка корректной передачи токенов от Lexer к NumberParser.
     • Проверка того, как DFA внутри Lexer корректно классифицирует лексемы.
     • Тестирование полного цикла: входная строка → Lexer → NumberParser → числовой результат.
3. Функциональное тестирование (Functional Testing) / Тестирование «чёрного ящика»:
   • Что проверяется: Соответствие поведения программы её спецификации с точки зрения конечного пользователя, без знания внутренней структуры.
   • Примеры для нашей задачи:
     • Проверка, что для «сто двадцать пять» программа возвращает 125.
     • Проверка, что для «минус одна тысяча» программа возвращает -1000.

Сценарии тестирования

Разработка детальных сценариев тестирования критически важна для всесторонней проверки.

1. Позитивные сценарии (Positive Scenarios):
   • Цель: Убедиться, что программа корректно обрабатывает ожидаемый ввод.
   • Примеры:
     • Простые числа: «ноль», «пять», «семнадцать», «сорок», «двести», «тысяча», «десять тысяч».
     • Составные числа: «двадцать три», «сто один», «пятьсот сорок семь», «три тысячи сто двадцать один», «минус пять тысяч восемьсот девяносто девять».
     • Числа с родовыми формами: «одна тысяча», «две тысячи».
2. Негативные сценарии (Negative Scenarios):
   • Цель: Проверить, как программа реагирует на некорректный или неоднозначный ввод, и убедиться, что она выдаёт адекватные сообщения об ошибках или исключения.
   • Примеры:
     • Нечисловые слова: «привет», «тест», «яблоко сто».
     • Повторяющиеся или некорректные последовательности: «сто двадцать один один», «пятьсот сорок четыре пятьдесят» (дублирование разрядов или логические ошибки).
     • Неполные выражения: «минус», «тысячи», «двести десять тысяч» (за пределами диапазона).
     • Пустая строка: «»
3. Граничные значения (Boundary Value Testing):
   • Цель: Тестирование значений на границах допустимого диапазона, так как именно здесь часто возникают ошибки.
   • Примеры для диапазона от -10000 до 10000:
     • Минимальное значение: «минус десять тысяч» (-10000).
     • Значения, близкие к минимуму: «минус девять тысяч девятьсот девяносто девять» (-9999).
     • Переход через ноль: «минус один» (-1), «ноль» (0), «один» (1).
     • Значения, близкие к максимуму: «девять тысяч девятьсот девяносто девять» (9999).
     • Максимальное значение: «десять тысяч» (10000).
4. Тестирование исключений (Exception Testing):
   • Цель: Проверить, что программа корректно генерирует и обрабатывает исключения при обнаружении ошибок, как это было описано в разделе о C#.
   • Примеры:
     • Ввод «сто яблоко» должен вызывать InvalidNumberFormatException или аналогичное.
     • Ввод «пятьсот тысяча» (грамматически некорректно) также должен привести к исключению.

Валидация программы

Валидация — это процесс оценки программного обеспечения на соответствие требованиям и ожиданиям пользователя. Она фокусируется на вопросе: «Создали ли мы правильный продукт?». Валидация может осуществляться на различных стадиях жизненного цикла разработки.

Основные атрибуты качества программного обеспечения, согласно стандарту ISO/IEC 25010, которые необходимо учитывать при валидации:

1. Функциональная пригодность:
   • Функциональная полнота: Обеспечивает ли программа все заявленные функции? (Да, переводит числа прописью в числовой формат).
   • Функциональная корректность: Выполняет ли программа свои функции точно и без ошибок? (Результаты тестирования должны это подтвердить).
   • Функциональная уместность: Соответствуют ли функции программы её назначению?
2. Надёжность:
   • Зрелость: Насколько часто возникают сбои? (Минимизация ошибок через тестирование).
   • Восстанавливаемость: Насколько легко программа восстанавливается после сбоев? (Обработка исключений помогает в этом).
   • Отказоустойчивость: Как программа реагирует на ошибки и некорректные условия?
3. Производительность:
   • Время отклика: Насколько быстро программа обрабатывает ввод?
   • Пропускная способность: Сколько операций может выполнить за единицу времени?
   • Эффективность использования ресурсов: Насколько эффективно используются ресурсы процессора и памяти? (Выбор int как типа данных способствует этому).
4. Удобство использования:
   • Насколько легко пользователю взаимодействовать с программой? (В случае консольной утилиты — понятный ввод/вывод).
5. Безопасность:
   • Защищена ли программа от несанкционированного доступа или использования? (Для данной задачи менее критично, но важно для общего качества ПО).
6. Тестируемость:
   • Насколько легко тестировать программу? (Модульная архитектура способствует этому).

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

Возможности расширения функциональности программы

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

Расширение для более сложных числовых выражений

Текущий диапазон от -10000 до 10000 покрывает лишь базовые сценарии. Однако в реальном мире часто встречаются гораздо более сложные числовые конструкции:

1. Дробные числительные:
   • Примеры: «одна целая две десятых», «три с половиной», «ноль целых двадцать пять сотых».
   • Усложнение ДКА: Потребуется ввести новые состояния для слов «целая», «десятых», «сотых», «половина» и т.д. Также необходимо будет отслеживать положение запятой и соответствующим образом агрегировать дробную часть числа.
   • Алгоритм: Семантические действия должны будут поддерживать накопление дробной части с использованием плавающей точки или десятичных типов данных (например, double или decimal в C#).
2. Порядковые числительные:
   • Примеры: «первый», «второй», «сто пятый», «две тысячи десятый».
   • Усложнение ДКА: Потребуются отдельные состояния и правила для распознавания порядковых числительных, которые часто имеют иные суффиксы и грамматические формы по сравнению с количественными.
   • Алгоритм: Вместо прямого преобразования в число, программа должна будет вернуть порядковое значение (например, 1-й, 2-й) или флаг, указывающий на порядковый тип.
3. Большие числа:
   • Расширение диапазона: От миллионов до миллиардов, триллионов и выше.
   • Усложнение структуры ДКА: Основной принцип агрегации тысяч будет масштабирован. Потребуются дополнительные состояния для «миллион», «миллионов», «миллиард» и т.д., а также более сложная логика для управления множителями разрядов.
   • Алгоритм: Семантические действия потребуют использования более крупных числовых типов (например, long или BigInteger в C#), а также циклического применения логики умножения на 1000, 1000000 и т.д.
4. Контекстный анализ:
   • Примеры: «В книге сто страниц» или «У меня две тысячи рублей».
   • Усложнение: Это выходит за рамки чисто лексического анализа и требует элементов синтаксического и даже семантического анализа всего предложения. ДКА будет использоваться как часть более сложного парсера естественного языка, который сможет извлекать числовые выражения из контекста предложения и игнорировать нечисловые слова.

Адаптация для других языков

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

Рассмотрим пример английского языка:

• Грамматические отличия:
  • Отсутствие склонений: В отличие от русских числительных, английские не склоняются по родам, числам и падежам, что значительно упрощает их грамматическую обработку. Например, «one», «two» всегда остаются «one», «two» вне зависимости от контекста.
  • Союз «and»: Часто используется между сотнями и десятками, например, «one hundred and twenty-three» (сто двадцать три).
  • Специфические формы: Для десятков (e.g., «twenty», «thirty») и чисел от 13 до 19 (e.g., «thirteen», «nineteen») существуют уникальные слова.
  • Разделение больших чисел: При записи больших чисел принято разделять группы по три цифры запятыми (например, 1,765 — «one thousand, seven hundred and sixty-five»).
  • Формы «hundred», «thousand», «million»: Обычно используются в единственном числе, если перед ними стоит конкретное числительное («two hundred»), но могут принимать окончание множественного числа «-s» при использовании в качестве существительных для обозначения неопределенного количества («hundreds of years»).
• Требования к ДКА:
  • Потребуется новый набор лексических единиц (e.g., «one», «two», «ten», «eleven», «twenty», «hundred», «thousand», «million»).
  • Новая структура состояний и переходов, отражающая грамматику английских числительных, включая обязательное/необязательное использование «and».
  • Пересмотренные семантические действия для агрегации значений.

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

Заключение

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

Мы начали с фундаментальных концепций лексического анализа, определив его роль как первого и критически важного этапа в обработке текстовых данных. Глубокое погружение в теорию детерминированных конечных автоматов (ДКА) позволило нам понять их структуру, принципы работы и широкие возможности применения не только в компиляторах, но и в других областях, где требуется надёжное распознавание паттернов. Была подчёркнута неразрывная связь регулярных выражений с ДКА, составляющая основу для автоматического построения анализаторов.

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

В разделе, посвящённом программной реализации на C#, мы представили архитектурные решения для моделирования ДКА с использованием классов и структур данных, а также предложили модульную структуру программы, включающую Lexer и NumberParser. Особое внимание было уделено обработке отрицательных чисел и механизмам работы с исключениями и некорректным вводом, что является залогом надёжности и устойчивости программного продукта. Выбор типа int для хранения результата был обоснован его оптимальностью для заданного диапазона.

Завершающим, но не менее важным этапом, стало обсуждение методов тестирования и валидации. Были предложены конкретные виды тестирования — модульное, интеграционное, функциональное, а также детальные сценарии, охватывающие позитивный, негативный и граничные случаи. Валидация программы с учётом атрибутов качества ПО по стандарту ISO/IEC 25010 подчеркнула стремление к созданию не просто работающего, но и качественного продукта.

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

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

Список использованной литературы

1. Ахо, А., Сети, Р., Ульман, Дж., Лам, М. Компиляторы. Принципы, технологии, инструменты. 2025. URL: https://m.vk.com/wall-54530371_460 (дата обращения: 07.11.2025).
2. Карпов, Ю.Г. Теория автоматов : учебник для вузов. СПб: Питер, 2003. 208 с.
3. Шилдт, Г. Полный справочник по C#. Москва: Издательский дом Вильямс, 2008. 752 с.
4. Теория автоматов и формальных языков. АОИ. URL: https://aoi.aspu.ru/matematika-i-informatika/teoriya-avtomatov-i-formalnyh-yazykov/ (дата обращения: 07.11.2025).
5. Лекции по теории автоматов. ELIBRARY.RU. URL: https://www.elibrary.ru/item.asp?id=38520359 (дата обращения: 07.11.2025).
6. ТЕОРИЯ АВТОМАТОВ. Томский политехнический университет. URL: https://www.tpu.ru/fcd-file/36367 (дата обращения: 07.11.2025).
7. Исключения и обработка исключений. C# | Microsoft Learn. URL: https://learn.microsoft.com/ru-ru/dotnet/csharp/fundamentals/exceptions/ (дата обращения: 07.11.2025).
8. Практическое руководство. Преобразование строки в число. C# | Microsoft Learn. URL: https://learn.microsoft.com/ru-ru/dotnet/csharp/how-to/parse-strings-to-numbers (дата обращения: 07.11.2025).
9. Целочисленные числовые типы (справочник по C#). Microsoft Learn. URL: https://learn.microsoft.com/ru-ru/dotnet/csharp/language-reference/builtin-types/integral-numeric-types (дата обращения: 07.11.2025).
10. Основы C#: Операции, Циклы, Условия, и Исключения. Виктор Комлев. URL: https://vkomlev.com/blog/ru/c-sharp-basics-operations-loops-conditions-and-exceptions/ (дата обращения: 07.11.2025).
11. C# числительные — прописью, преобразование числа в фразу. CodeLAB. URL: https://www.codelab.ru/articles/csharp/123/ (дата обращения: 07.11.2025).
12. Конечный автомат: что это такое, состояния и переходы, как создать простейший автомат. GitVerse Blog. URL: https://gitverse.ru/blog/finite-state-machine-theory-and-practice (дата обращения: 07.11.2025).
13. Конечный автомат. Википедия. URL: https://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 (дата обращения: 07.11.2025).
14. Конечные автоматы. Математический аппарат инженера. URL: http://www.math.ru/lib/books/djvu/mat_app/ingen_math_2.djvu (дата обращения: 07.11.2025).
15. Конечные автоматы в реальной жизни: где мы их используем и почему. Habr. URL: https://habr.com/ru/companies/yandex_praktikum/articles/564348/ (дата обращения: 07.11.2025).
16. Конечный автомат. URL: https://e-lib.gasu.ru/vuz/uch-posob/kopytov_kompilatory/kopytov_kompilatory.files/kopytov_kompilatory.pdf (дата обращения: 07.11.2025).
17. Автоматное программирование. IPR SMART. URL: https://www.iprbookshop.ru/74889.html (дата обращения: 07.11.2025).
18. Автоматные языки. ИРБИС64+ Электронная библиотека. URL: https://lib.sfu-kras.ru/elib/viewbook/bookView.aspx?id=305537&start=205 (дата обращения: 07.11.2025).
19. Умный парсер числа, записанного прописью. Habr. URL: https://habr.com/ru/articles/451474/ (дата обращения: 07.11.2025).
20. Парсите, а не валидируйте. Habr. URL: https://habr.com/ru/articles/499624/ (дата обращения: 07.11.2025).
21. Конвертер арабских чисел в русские числительные. Learn Russian Tools. URL: https://www.russiantools.ru/ru/numbers-to-russian-words (дата обращения: 07.11.2025).
22. Морфология русского языка 2: числительные, глаголы и неизменяемые части речи. Педагогический факультет Университета им. Масарика — IS MUNI, 2014. URL: https://is.muni.cz/el/1451/podzim2014/CJ2BP_MORG/um/morfologie_AJ_2_cislovky.pdf (дата обращения: 07.11.2025).