16 Основные виды бинарных отношений. Рефлексвное и транзитивное замыкание.

Бинарное отношение R ⊆ A × A называется:1)рефлексивным, если (a, a) ∈ R для каждого элемента a ∈ A; 2) иррефлексивным (а,а) ∉ R; 3)симметричным, если из того, что (a, b) ∈ R => (b, a) ∈ R для любых элементов a, b ∈ A; 4)антисимметричным (a, b) ∈ R => (b, a) ∈ R => a=b; 5)транзитивным (a, b) ∈ R и (b, c) ∈ R => (a, c) ∈ R для любых эл.a, b, c ∈ A.

Отношение, которое одновременно является рефлексивным, симметричным и транзитивным, называется отношением эквивалентности. R [a]R = {b|(a, b) ∈ R}. Бинарным отношением на мн-ве А наз: 1)предпорядком-если рефлексивно и транзитивно; 2)частичный порядок - рефлексивно, антисимметрично и транзитивно. -частичный порядок наз: линейный - у х для всех х,у ∈ А. мн-во А задано с частичным порядком , тогда А наз. частично упорядоченное мн-во. эл. а частично упорядоченное мн-ва А наз максим(мин), если из того что а х (х а) следует а=х. эл. а из А наз наибольшим(наимен) если х а(а х) для всех х∈А.

17 Пересечение и дополнение контекстно-свободных языков.

Теорема. Неверно, что для любых контекстно-свободных языков L₁ и L₂ язык L₁ ∩ L₂ тоже контекстно-свободный. Доказательство. Положим L1 = { a^mb^mcⁿ | m >= 0,n >= 0}и L2 = { a^mbⁿcⁿ | m >= 0,n >= 0} . Рассмотрим язык L = { aⁿbⁿcⁿ | n 0} над алфавитом { a, b, c} . Утверждение леммы: Пусть L — контекстно-свободныйязык над алфавитом Σ. Тогда найдётся такое натуральное число p, что для любого слова ω ∈ L длины не меньше p найдутся слова u, v, x, y, z ∈ Σ∗ , для которых верно uvxyz = ω, vy ≠ ε (то есть v ≠ ε или y ≠ ε), |vxy| <= p и uvⁱxyⁱz ∈ L длявсех i ∈ N. не выполняется ни для какого натурального числа p. Действительно, если uvxyz = a^pb^pc^p, |vy| > 0 и |vxy| <= p, то |vy|_a =0 или |vy|_c =0. Следовательно, |uvvxyyz|_a = p или |uvvxyyz|_c = p. Так как |uvvxyyz| > 3p,то uvvxyyz не ∈ L. Из этого можно заключить, что язык L не является контекстно-свободным. отсуда было доказано, что язык L1 ∩ L2 не является контекстно-свободным.

Теорема . Неверно, что для любого контекстно-свободного языка L ⊆ Σ^∗ язык Σ^∗ − L тоже контекстно-свободный. Доказательство. Положим L =Σ^∗ −{ aⁿbⁿcⁿ | n >=0} ,гдеΣ= { a, b, c}. Рассмотрим алфавит Σ= { a, b, c} .Язык L =Σ^∗ −{ aⁿbⁿcⁿ | n >=0} является линейным, поскольку L = L₁ ∪ L₂ ∪ (Σ^∗ − L₃), где языки L₁ = { a^mbⁿc^k | m ≠ n, k >= 0}и L₂ = { a^mbⁿc^k | n ≠ k, m >= 0} являются линейными, а язык L₃ = { a^mbⁿc^k | m >= 0,n >= 0,k >= 0} является автоматным и можно применить теорему 1:Каждый автоматный язык является право-линейным; и теоремму 2: Если L1 и L2 — линейные языки над алфавитом Σ,то L1 ∪ L2 тоже линейный язык. следовательно было доказано, что язык L является линейным (и следовательно, контекстно-свободным).

18 Пересечение контекстно-свободного языка с автоматным языком.

Теорема . Если L₁ — контекстно-свободный язык и L₂ —автоматный язык, то язык L₁ ∩ L₂ является контекстно-свободным. Доказательство. Пусть <N, Σ,P,S> — контекстно-свободная грамматика, порождающая язык L₁. Без ограничения общности можно считать, что множество P содержит только правила вида A → a и A → α, где A ∈ N , a ∈ Σ и α ∈ N^∗ . Пусть <Q, Σ, Δ,I,F> —конечный автомат, распознающий язык L₂. Без ограничения общности можно считать, что для каждого перехода <p, x, q> ∈ Δ выполняется равенство |x| =1. Построим контекстно-свободную грамматику < , , , >, порождающую язык L₁ ∩ L₂.Положим = { }∪ (Q × N × Q), P = { S →<p, S, q>| p ∈ I, q ∈ F }∪{<p, A, q>→ a |<p, a, q >∈ Δ, (A → a) ∈ P }∪{<p₀,A,p_n>→<p₀,B₁,p₁> ... <p_{n− 1},B_n,p_n>|(A → B₁ ...B_n) ∈ P, p₀ ∈ Q,...,p_n ∈ Q} , где — новый символ (не принадлежащий множеству Q× N × Q).