close

Вход

Забыли?

вход по аккаунту

?

О логической определяемости языков на конечных автоматах.

код для вставкиСкачать
2. Субботин Ю.Н. Новый кубический элемент в МКЭ // Тр. Института математики
и механики УрО РАН. 2005. Т. 11, № 2. С. 120–130.
3. Куприянова Ю.В. Об оценке производной по направлению Эрмитова сплайна на
треугольнике // Математика. Механика: Сб. науч. тр. Саратов, 2006. Вып. 8. С. 59–61.
УДК 519.4
В.А. Молчанов
О ЛОГИЧЕСКОЙ ОПРЕДЕЛЯЕМОСТИ ЯЗЫКОВ
НА КОНЕЧНЫХ АВТОМАТАХ
В работе [1] предложен унифицированный подход к теории языков конечных автоматов на основе методов нестандартного анализа [2]: здесь естественно введено понятие распознаваемого автоматом Буши языка произвольных слов и описан класс RecB (A) таких языков. В последующей работе [3]
с помощью методов нестандартного анализа естественно введено понятие
языка произвольных слов, распознаваемого конечной полугруппой, и описан
класс RecS (A) таких языков. Проведенные исследования показывают, что
в отличие от равносильности понятий распознаваемых автоматами и полугруппами языков конечных слов [4] класс RecS (A) значительно шире класса
RecB (A). С другой стороны, в работе [5] введено понятие обобщенного автомата Мюллера и доказано, что класс RecM (A) распознаваемых такими
автоматами языков произвольных слов содержит класс RecS (A). С целью
доказательства обратного включения RecM (A) ⊂ RecS (A) в настоящей статье развивается теоретико-модельный подход к языкам произвольных слов,
разработанный Буши [6] для языков конечных слов и языков бесконечных
вправо слов.
В основе такого подхода лежит возможность описания языков над конечным алфавитом A формулами языка L монадической логики 2-го порядка [7]
сигнатуры Ω = {<, (Ra )a∈A }, состоящей из одного символа бинарного предиката < и семейства символов унарных предикатов Ra (a ∈ A). Алфавит
такого языка L, помимо символов < и Ra , содержит знак равенства =, символы логических связок ¬, ∧, ∨, ⇒ и кванторов ∀, ∃, предметные переменные
x, y, . . . , предикатные унарные переменные X, Y, . . . и скобки. Атомарными
формулами языка L являются выражения x = y, x < y, Ra (x), X(x), где
x, y – предметные переменные и X – предикатная унарная переменная. Из
таких атомарных формул с помощью логических связок и кванторов обычным образом [7] строятся формулы языка L.
Интерпретируются
формулы языка L в алгебраических Ω-системах M =
M
= M, <M , (Ra )a∈A с помощью отображения θ1 предметных переменных в
элементы множества M и отображения θ2 предикатных переменных в подмножества множества M. При этом символы предикатов < и Ra (a ∈ A)
57
интерпретируются как сигнатурные отношения <M и RaM (a ∈ A) алгебраической Ω-системы M. В результате такой интерпретации каждая формула Φ
языка L становится истинным или ложным утверждением о свойствах алгебраической Ω-системы M. Например, атомарная формула x = y истинна, если
θ1 (x) = θ1 (x), формула x < y истинна, если θ1 (x) <M θ1 (x), формула Ra (x)
истинна, если θ1 (x) ∈ RaM , и формула X(x) истинна, если θ1 (x) ∈ θ2 (X).
В случае истинности полученного из формулы Φ утверждения о системе M
будем говорить, что формула Φ выполняется на алгебраической Ω-системе
M при интерпретирующем отображении θ = (θ1 , θ2 ) и записывать M |=θ Φ.
Будем говорить, что формула Φ тождественно истинна на алгебраической
Ω-системе M и записывать M |= Φ, если M |=θ Φ при любом интерпретирующем отображении θ = (θ1 , θ2 ).
Рассмотрим конечный алфавит A. Пусть Wf in (A) – множество всех конечных слов, W → (A) – множество всех бесконечных вправо слов, W ← (A) –
множество всех бесконечных влево слов, W ↔ (A) – множество всех бесконечных в обе стороны слов и W (A) = Wf in (A) ∪ W → (A) ∪ W ← (A) ∪ W ↔ (A)
– множество всех слов над алфавитом A. Подмножества W (A) называются
языками произвольных слов над алфавитом A.
Поскольку каждое слово w
∈
W (A) можно рассматривать
как отображение некоторого отрезка (конечного или бесконечного в любую сторону) множества целых чисел Z в алфавит A, то
для слова w канонически определяется алгебраическая Ω-система
Mw = (Z, <, (Ra )a∈A ) , где < – отношение сравнения целых чисел и
−1
Ra = w (a) для каждого a ∈ A. Будем говорить, что слово w удовлетворяет
формуле Φ языка L, если Mw |= Φ. Множество всех слов w ∈ W (A),
удовлетворяющих условию Mw |= Φ, называется спектром формулы Φ и
обозначается символом S(Φ).
Для сокращения записи формул введем следующие обозначения:
˙ := (x < y ∧ ¬∃z(x < z < y)),
x ≤ y := (x < y ∨ x = y), x<y
_
Ra (x), x = min := (D(x) ∧ ∀y(D(y) ⇒ x ≤ y)),
D(x) :=
a∈A
x = max := (D(x) ∧ ∀y(D(y) ⇒ y ≤ x)).
Так как формула D(x) в алгебраической Ω-системе Mw определяет множество dom w, то в языке L найдутся такие формулы Φf in , Φ→ , Φ← и Φ↔ , которые определяют соответственно свойства конечности, бесконечности вправо,
бесконечности влево и бесконечности в обе стороны слова w, т.е. выполняются равенства S(Φf in ) = Wf in (A), S(Φ→ ) = W → (A), S(Φ← ) = W ← (A) и
S(Φ↔ ) = W ↔ (A). Например, слово w конечно в том и только том случае,
если оно удовлетворяет формуле Φf in := ∃x∃y(x = min ∧ y = max), и
58
бесконечно вправо, если оно удовлетворяет формуле
Φ→ := ∃x(x = min ∧ ∀y∃z(y < z ∧ D(z))).
Пусть A = (Q, A, E, c, F, I, J , T ) – некоторый обобщенный автомат Мюллера [5] с множеством состояний Q = {1, 2, . . . , n}, множеством переходов
E ⊂ Q × A × Q, центральным состоянием c ∈ Q, множеством заключительных состояний F ⊂ Q, левой и правой таблицами состояний I, J и таблицей
состояний T . Из результатов работы [7] следует, что существование в автомате A пути с меткой w ∈ W (A) можно определить с помощью формулы


^
Ψ :=  ¬∃x (D(x) ∧ Xi (x) ∧ Xj (x)) ∧

i6=j

˙ ∧ D(x) ∧ D(y) ⇒
∧ ∀x∀y x<y
_
(i,a,j)∈E

(Xi (x) ∧ Ra (x) ∧ Xj (y)) .
При этом в языке L найдутся такие формулы Ψ1 , Ψ2 , Ψ3 и Ψ4 , которые
определяют успешность такого пути соответственно для конечного, бесконечного вправо, бесконечного влево и бесконечного в обе стороны слова w.
Например, конечное слово w успешно в автомате A в том и только
том слуW
чае, если оно удовлетворяет соотношению Ψ1 := Xc (min) ∧ i∈F Xi (max),
и бесконечное вправо слово w успешно в автомате A в том и только том
случае, если оно удовлетворяет условию
!
_ ^
Ψ2 := Xc (min) ∧
(∀x (D(x) ⇒ ∃y (x < y ∧ Xi (y)))) .
B∈J
i∈B
Теорема. Для обобщенного автомата Мюллера A спектр формулы
∃X1 . . . ∃Xn (Ψ0 ∧ (Φf in ⇒ Ψ1 ) ∧ (Φ→ ⇒ Ψ2 ) ∧ (Φ← ⇒ Ψ3 ) ∧ (Φ↔ ⇒ Ψ4 ))
совпадает с распознаваемым автоматом A языком произвольных слов.
БИБЛИОГРАФИЧЕСКИЙ СПИСОК
1. Molchanov V.A. Nonstandard approach to general rational languages // Contributions
to General Algebra. 2001. Vol. 13. P. 233–244.
2. Альбеверио С., Фенстад Й., Хеэг-Крон Р., Линдстрем Т. Нестандартные методы
в стохастическом анализе и математической физике. М.: Мир, 1990. 616 с.
3. Молчанов В.А. О распознавании языков произвольных слов конечными полугруппами // Известия Сарат. ун-та. Нов. сер. 2006. Т. 6. Сер. Математика. Механика. Информатика, вып. 1/2. С. 96–108.
4. Pin J.E. Finite semigroups and recognizable languages: an introduction // Semigroups,
Formal Languages and Groups, NATO ASI Series C: Mathematical and Physical Sciences.
1993. Vol. 466. P. 1–32.
59
5. Молчанов В.А. О распознавании языков полугруппами и автоматами // Математика. Механика: Сб. науч. тр. 2006. Вып. 8. Саратов: Изд-во Сарат. ун-та, С. 83–86.
6. Büchi J.R. Weak second-order arithmetic and finite automata // Z. Math. Logik and
Grundl. Math. 1960. Vol. 6. P. 66–92.
7. Perrin D., Pin J.E. Semigroups and automata on infinite words // Semigroups,
Formal Languages and Groups, NATO ASI Series C: Mathematical and Physical Sciences.
1993. Vol. 466. P. 49–72.
УДК 519.853.3 + 517.518.82
Е.А. Нарыжная
О НАИЛУЧШЕМ ПРИБЛИЖЕНИИ
НЕПРЕРЫВНОЙ СЕГМЕНТНОЙ ФУНКЦИИ
АЛГЕБРАИЧЕСКИМ ПОЛИНОМОМ
1. Пусть g1 (t) и g2 (t) – непрерывные на отрезке [c, d] функции, причем
g1 (t) < g2 (t) при t ∈ [c, d]. Обозначим через Pn (A, t) = a0 + a1 t + . . . +
+an tn полином n-й степени с вектором коэффициентов A = (a0 , a1 , . . . , an ).
Φ(t) = [g1 (t), g2 (t)] – сегментная функция (с.ф.), сопоставляющая каждому
значению t ∈ [c, d] соответствующий сегмент.
Рассмотрим следующую задачу о наилучшем приближении с.ф. Φ(t) полиномом n-й степени:
df
ϕ(A) = max (ρ(Φ(t), Pn (A, t)) + ρ(Pn (A, t), Φ(t))) −→ inf ,
t∈[c,d]
(1)
A∈Rn+1
где
ρ(Φ(t), Pn (A, t)) = max {g2 (t) − Pn (A, t), Pn (A, t) − g1 (t)}
есть уклонение с.ф. от полинома,
ρ(Pn (A, t), Φ(t)) = max {Pn (A, t) − g2 (t), g1 (t) − Pn (A, t), 0}
есть уклонение полинома от с.ф.
df
Очевидно, что функция F (A, t) = ρ(Φ(t), Pn (A, t)) + ρ(Pn (A, t), Φ(t)) выпукла по A на Rn+1 при каждом фиксированном t ∈ [c, d]. Следовательно
(см., например [1]), и функция ϕ(A) является выпуклой на Rn+1 . Обозначим
через
df
R(A) = {t ∈ [c, d] : ϕ(A) = F (A, t)} ,
g2 (ti ) + g1 (ti )
∗
>0 ,
R1 (A) = t ∈ R(A) : Pn (A , ti ) −
2
g
(t
)
+
g
(t
)
df
2 i
1 i
R2 (A) = t ∈ R(A) : Pn (A∗ , ti ) −
<0 ,
2
df
60
Документ
Категория
Без категории
Просмотров
3
Размер файла
183 Кб
Теги
логические, языков, конечный, автомата, определяемость
1/--страниц
Пожаловаться на содержимое документа