Проверка принадлежности регулярному языку

 

Следующий важный вопрос состоит в том, принадлежит ли данная цепочка w данному регулярному языку L. В то время, как цепочка w задается явно, язык L представляется с помощью автомата или регулярного выражения.

Если язык L задан с помощью ДКА, то алгоритм решения данной задачи очень прост. Имитируем ДКА, обрабатывающий цепочку входных символов w, начиная со стартового состояния. Если ДКА заканчивает в допускающем состоянии, то цепочка w принадлежит этому языку, в противном случае — нет. Этот алгоритм является предельно быстрым. Если |w| = n и ДКА представлен с помощью подходящей структуры данных, например, двухмерного массива (таблицы переходов), то каждый переход требует постоянного времени, а вся проверка занимает время O(n).[5]

Если L представлен способом, отличным от ДКА, то преобразуем это представление в ДКА и применим описанную выше проверку. Такой подход может занять время, экспоненциально зависящее от размера данного представления и линейное относительно |w|. Однако, если язык задан с помощью НКА или ε-НКА, то намного проще и эффективнее непосредственно проимитировать этот НКА. Символы цепочки w обрабатываются по одному, и запоминается множество состояний, в которые НКА может попасть после прохождения любого пути, помеченного префиксом цепочки w. Идея такой имитации была представлена на рис. 2.10.

Если длина цепочки w равна n, а количество состояний НКА равно s, то время работы этого алгоритма равно O(ns2). Чтобы обработать очередной входной символ, необходимо взять предыдущее множество состояний, число которых не больше s, и для каждого из них найти следующее состояние. Затем объединяем не более s множеств, состоящих из не более, чем s состояний, для чего нужно время O(s2).

Если заданный НКА содержит ε-переходы, то перед тем, как начать имитацию, необходимо вычислить ε-замыкание. Такая обработка очередного входного символа a состоит из двух стадий, каждая из которых занимает время O(s2). Сначала для предыдущего множества состояний находим последующие состояния при входе a. Далее вычисляем ε-замыкание полученного множества состояний. Начальным множеством состояний для такого моделирования будет ε-замыкание начального состояния НКА.

И наконец, если язык L представлен регулярным выражением, длина которого s, то за время O(s) можно преобразовать это выражение в ε-НКА с числом состояний не больше 2s. Выполняем описанную выше имитацию, что требует O(ns2) времени для входной цепочки w длиной n.[4]

 

Пример проверки имени пользователя на валидность

 

Листинг кода:

package caesar_сipher;

import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class Main {

public static void main(String[] args){
System. out. println("Cool check:");

System. out. println(checkWithRegExp ("_@BEST"));
System. out. println(checkWithRegExp ("nazym"));
System. out. println(checkWithRegExp ("vo"));
System. out. println(checkWithRegExp ("Z@OZA"));

System. out. println("\nDumb check:");

System. out. println(dumbCheck ("_@BEST"));
System. out. println(dumbCheck ("aruzhan"));
System. out. println(dumbCheck ("vo"));
System. out. println(dumbCheck ("Z@OZA"));
}

public static boolean checkWithRegExp(String userNameString){
Pattern p = Pattern. compile ("^[a-z0-9_-]{3,15}$");
Matcher m = p.matcher(userNameString);
return m.matches();
}

public static boolean dumbCheck(String userNameString){

char [] symbols = userNameString.toCharArray();
if (symbols. length < 3 || symbols. length > 15) return false;

String validationString = "abcdefghijklmnopqrstuvwxyz0123456789_";

for (char c: symbols){
if (validationString.indexOf(c)==-1) return false;
}

return true;
}
}

 

результат кода:

 

 

 

Как видим, в нашей программе есть два метода для проверки имени пользователя на валидность. Первый метод checkWithRegExp(String userNameString) использует регулярное выражение для проверки валидности, а второй dumbCheck(String userNameString) делает проверку "Вручную".

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

 

 

Заключение

 

Существует много операций, результат применения которых к регулярным языкам также является регулярным языком. В их числе объединение, конкатенация, замыкание (итерация), пересечение, дополнение, разность, обращение, гомоморфизм (замена каждого символа соответствующей цепочкой) и обратный гомоморфизм. Конечные автоматы, безусловно, полезны для реализации логики искусственного интеллекта в играх. Они могут быть легко представлены в виде графа, что позволяет разработчику увидеть все возможные варианты.

Существует алгоритм, который по такому заданному представлению регулярного языка, как автомат или регулярное выражение, определяет, является ли представленный язык пустым множеством.

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

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

 

 

Список литературы

 

1. Карпов Ю. Теория автоматов. – СПб.: Питер, 2002. - 224 с.

2. Хопкрофт Д. и др. Введение в теорию автоматов, языков и вычислений. – М.: Вильямс, 2002.

3. Гордеев А., Молчанов Ю. Системное программное обеспечение. – СПб.: Питер, 2001. - 736 c.

4. Гинзбург С., Роуз Дж. Об инвариантности классов языков относительно некоторых преобразований. - Кибернетический сборник, Новая серия, вып. 5. - М.: Мир, 1968. - С. 138-166.

5. Хопкрофт Дж. Алгоритм для минимизации конечного автомата. - Кибернетический сборник, Новая серия, вып. 11. - М.: Мир, 1974. - С. 177–184.

6. Клини С.К. Представление событий в нервных сетях. - сб. “Автоматы”. - М.: ИЛ, 1956. - С. 15–67.

7. Мур Э.Ф. Умозрительные эксперименты с последовательностными машинами. — сб. “Автоматы”. — М.: ИЛ, 1956. — С. 179–210.

8. http://www.quizful.net/post/Java-RegExp

9. https://ru.wikipedia.org