что такое неопределенность в алфавите в теории автоматов? - PullRequest
Новая
       19

что такое неопределенность в алфавите в теории автоматов?

0 голосов
/ 26 июня 2018

Я просто новичок в области автоматов. Я прочитал много статей и видел много видео. Я застрял в некоторых первых темах. Это может быть легко для других. но, потратив много времени, я все еще не могу этого понять. ТЕМА: Неопределенность в алфавите

Алфавит = {A, Aa, Bab, D} и строка s = AababA

и автор говорит, что это неоднозначный алфавит, потому что, когда компьютер читает его, он читает слева направо. После заглавной буквы A, снова A, который является префиксом маленького a, создаст двусмысленность. Буква (символ) не должна быть префиксом новой буквы. Более того, автор говорит. мы будем маркировать его (AababA) двумя способами:

  • (Aa) (баб) (A)
  • (A) (abab) (A)

после этого, первое в порядке, второе не в порядке из-за неоднозначности в определении алфавита выше.

  1. Что такое процедура токенизации вышеприведенной строки двумя способами? Есть ли какое-то конкретное правило?
  2. Как неоднозначен алфавит из-за второй группы.
  3. Если он недействителен из-за префикса A, то как? Какова роль префикса в неоднозначности алфавита?
  4. Если мы не думаем о префиксе и просто сопоставляем группу из двух строк с указанным выше алфавитом, то мы можем легко определить, что секунда не совпадает с указанным выше алфавитом, тогда зачем нам обсуждать этот префикс?

Надеюсь, этот вопрос будет сочтен важным, поэтому этот ответ поможет мне избавиться от этой путаницы. Я буду очень благодарен.

1 Ответ

0 голосов
/ 12 сентября 2018

Автор выбрал запутанный пример. Если вы поделитесь источником, где вы взяли этот пример, я мог бы дать лучший ответ, но я бы сказал, что в этом случае нет практической двусмысленности. Если вы видите Aa, вы можете знать, что первая лексема должна быть «Aa», потому что ничто в алфавите не начинается с «a».

Для более простого примера рассмотрим алфавит {A, a, Aa} и строку «AAaAaaA»

Вы можете сделать это следующим образом: 

(A) (A) (a) (A) (a) (a) (A)
(A) (Aa) (A) (a) (a) (A)
(A) (A) (a) (Aa) (a) (A)
(A) (Aa) (Aa) (A)

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

Теперь давайте вернемся к вашему примеру, но давайте немного изменим строку: «AababAe».

Вы можете токенизировать строку следующими способами: 

(Aa) (bab) (A) <error>
(A) <error>

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

...