Идентификация имен: метод линейного списка

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

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

У этого метода есть лишь один недостаток: поиск по длинному списку занимает много времени. Если имеется М слов, то ожидаемое число сопоставлений для нахождения одного, случайно выбранного слова, равно (М+1)/2. Время поиска по длинному списку значительно уменьшается. если элементы упорядочены лексикографически (например, по алфавиту).

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

Вопросы и упражнения

Укажите достоинства и недостатки метода линейного списка.

Контекстно-свободные языки

Если язык L порожден контекстно-свободной грамматикой, то его называют контекстно-свободным языком.

Теорема: любой автоматный язык является КС-языком. Обратное не верно.

Пример:

S®aSb|ab - КС язык, но не является автоматным.

Вопросы и упражнения

1. Какой язык называется контекстно-свободным?

2. Приведите пример (отличный от данного в п.п.8) КС-языка, не являющегося автоматным.