Конечные автоматы

[iad58]

В этом году в магистр(ант)ской программе, в которой я преподаю введение в компьютерную лингвистику и программирование на Удаве, группа очень интересная. Шесть слушательниц, все из разных филологий: по одной из болгарской, венгерской, германской, испанской, португальской и французской.

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

Ниже следует задача.

---

Конечный автомат на фиг. 1 распознает формальный язык, состоящий из всех форм английского глагола do в настоящем времени изъявительного наклонения, то есть {do, does}.

Автоматы на фиг. 2 тоже распознают по формальному языку, состоящему из всех форм одного глагола в настоящем времени изъявительного наклонения. Языки, которым принадлежат глаголы, — болгарский, венгерский, испанский, немецкий, португальский и французский (в алфавитном порядке), а формы 1 л. ед. ч. глаголов — {дяна, fais, megyek, puedo, sehe, tenho} (тоже в алфавитном порядке). Этикеты ребер пропущены.

1. Определите, который из автоматов соответствует глаголу Вашего профильного языка.
2. Восстановите в нем этикеты ребер. (Каждое ребро означает прочтение ровно одной буквы, но она не везде единственно возможная, т.е. некоторые ребра, возможно, придется пометить более чем одной буквой.)

Comments

[lemberger]

Так, французский нашел. Сейчас примусь за немецкий.

[lemberger]

Ага, и немецкий вижу.

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

[utnapishti]

Я нашёл немецкий, причём это был не один из двух автоматов, о которых я думал сначала.

[enemyoflj]

Я нашёл немецкий (доказательным образом, то есть убедившись заодно, что остальные картинки неизоморфны этой) и стал решать задачу, образовавшуюся в результате моего невежества: можно ли восстановить испанский по двум глагольным формам, которые мне точно известны? Оказалось, что нет. В общем, тут возникают всякие интересные вопросы о том, какого минимального набора форм достаточно для отделения подходящих автоматов от неподходящих.

[iad58]

Да, задача предполагает, что ищущий какой-то определенный язык знает всю парадигму на нем. Но тоже возникают вопросы: как быть, если есть какие-то малоупотребительные формы (альтернативные или нет), должны ли они включаться? Мой английский автомат не распознает форм dost и doth, хотя они относятся к новоанглийскому языку, только стилистически маркированны. В других языках могут быть похожие ситуации.

[lemberger]

В венгерском примере gy за одну букву считается?

[iad58]

Нет, за две.