Задачи по теории формальных языков

[PSP]

Как решить следующие задачи по теории формальных языков? Никто не подскажет?

1)По заданному конечному автомату Н построить праволинейную грамматику G, задающую формальный язык L = L(H). б) Указать все простые ориентировочные пути, ведущие из начальной вершины автомата в какую-либо заключительную.
в) Указать все простые циклы автомата. г) Дать описание языка L(H) с помощью регулярного выражения.
H = ((V, E), S1, S, F, p), V = {S, A, B, C, D}; S1 = {a, b, c}; S; F = {C,D}; p(S, A) = a, p(A, B) = b, p(A, C) = c, p(B, S) = a, p(B, D) = b, p(C, D) = c.
д) Написать слово, принадлежащее языку L(H), и соответствующее пути из S в D, содержащем в точности два цикла.


2)Для данного конечного автомата H построить конечный детерминированный автомат H1 , представляющий тот же самый язык, что и автомат Н.
H = ((V, E), S1 , S, F, p), V = {1, 2, 3}; S1 = {a, b}; S = {1}; F = {3}; p(1, 2) = {a, b}, p(1, 3) = a, p(2, 1) = a, p(2, 3) = b, p(3, 2) = {a, b}.
(Нужно для дочери знакомой,у неё нет выхода в интернет)

[sonte]

Девочку не Светой ли зовут?

Задачи очень просты, их легче решить, чем набить в форуме решение. Первая фактически на применение определений, пункты (а)-(г) указывают последовательные шаги решения (кстати, пути - ориентированные, а не ориентировочные). Ответ в (г), если я не напутал: a(ba)*(bb|cc).
Вторая - на применение теоремы об эквивалентности недетерминированного и детерминированного автомата, надо тупо повторить конструкцию доказательства для данного H.

В общем, посоветуйте девочке потратить два-три часа и прочитать несколько страниц учебника или конспекта.

[PSP]

sonte писал(а):

Девочку не Светой ли зовут

Да, она из институтта-интерната для инвалидов-опорников...Просто у неё методичка какая то дурацкая...

[Dan_Te]

Если я правильно понимаю, то

PSP писал(а):

H = ((V, E), S1, S, F, p), V = {S, A, B, C, D}; S1 = {a, b, c}; S; F = {C,D}; p(S, A) = a, p(A, B) = b, p(A, C) = c, p(B, S) = a, p(B, D) = b, p(C, D) = c.

означает следующее:
граф с вершинами V, из которых начальная S и конечные C и D, на ребрах написаны буквы из алфавита S1, а какие есть ребра и что на них написано, задает функция p(,). Если это нарисовать, то получится вот что:


Неясно, зачем нужно ребро из C в D. Одно из трех: либо оно не нужно, либо C - не терминирующая вершина, либо я не понял задачу. Но если забыть про этот момент, то можно сразу ответить на пункты б, в, д первой задачи. Чтобы построить праволинейную грамматику и регулярное выражение, надо знать определения, что это такое (у меня где-то было, попробую посмотреть), но сделать это будет несложно, потому что граф совсем простой.

[Dan_Te]

Пока я рисовал, уже все объяснили =))

sonte писал(а):

Ответ в (г), если я не напутал: a(ba)*(bb|cc).

Глядя на граф, хочется сказать a(baa)*(bb|cc).

[sonte]

Dan_Te, C и D - не терминальные, а допускающие состояния. Автомат читает символ из входного потока и переходит в следующее состояние по стрелке с этой меткой. Если автомат в допускающем состоянии, когда слово дочитано, - слово принадлежит языку, иначе (или если встретился неожиданый символ) - нет.
И Вы правы, a(baa)*(bb|cc).

PSP, я затрудняюсь порекомендовать хорошую книжку. Моя любимая - Sipser M. Introduction to the theory of computation, она прекрасно, очень понятно написана, но на английском. Под рукой ещё оказалась методичка Пентуса, она заформализована до ужаса, но там есть список литературы (думаю, исчерпывающий).

[PSP]

Под рукой методичка проф. А.В.Тищенко...Монстр какой-то...Эаформализировано не просто до ужаса,а куда уж дальше...
Определение праволинейной(регулярной) грамматики:
каждая продукция из Pимеет вид или A -> aB, A -> \epsilon, где A, B - нетерминальные символы, а a -терминальный символ.
( \epsilon -пустое слово )

[незваный гость]

Мне кажется, что a(baa)*(bb|cc|c). Поскольку C -- допускающее состояние. Но я охотно допускаю, что неправ.

Я люблю "Грис Д. Построение компиляторов для цифровых вычислительных машин". Книга немного устарела, но очень понятна и практична. Как-то менее монографична, что ли.

[незваный гость]

Я основательно подзабыл классификацию грамматик, поэтому построю пример, удовлетворяющий определению выше:

S $\to$ a A.
A $\to$ c C.
C $\to$ c D.
C $\to$ $\epsilon$.
D $\to$ $\epsilon$.
A $\to$ b B.
B $\to$ b D.
B $\to$ a S.

[Dan_Te]

незванный гость писал(а):

Мне кажется, что a(baa)*(bb|cc|c). Поскольку C -- допускающее состояние. Но я охотно допускаю, что неправ.

Если, как написал sonte, мы можем заканчивать слово как в C, так и в D, то получается именно так.

[sonte]

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

[PSP]

Тема закрыта,всё решили