|
Тема |
Re: Задачка за регулярен израз [re: Пиprиш] |
|
Автор | няkoй (Нерегистриран) | |
Публикувано | 08.03.04 09:23 |
|
|
Mylord е напълно прав, че задачата е нерешима.
Ще дам много по-ясни аргументи, защо!
Добре известно е, че регулярните изрази генерират точно това, което може да генерира ДЕТЕРМИНИРАН КРАЕН АВТОМАТ. Това последното е грубо казано (и доста тъпо и неточно) множество от кръгчета - състояния, които са свързани със стрелкички на които има буквички. Обикаляйки през кръгчетата на изхода пишем буквичките, през които сме минали.
Нека имаме автомат, който решава нашата задача. Следователно всички думи от вида:
01,0011,000111,00001111,...
трябва да се разпознават. Но "кръгчето" на смяната 0-1 в горните примери тлябва винаги да е различно. Например ако във втори и трети е едно и също, тогава може да се генерира погрешна дума 00111. Да отбележим, че детерминирания краен автомат има краен брой състояния, а "средните" кръгчета в горната редица са безкраен брой.
Какво повече да добавя?
|
| |
|
|
|