Выборка теории с экзамена (2013) (1134914)
Текст из файла
Теория 2013, 3 варианта, ответы с фоток у которых ‘+’.* = не точно. Если есть ещё фотки – присылайте на roman@dovgopol.com, обновлюЕсли не нашли свой вопрос здесь – пишем «Да, по определению». Серьёзно.1.1 Верно ли, что для всякого НКА существует однозначная регулярная грамматика, порождающаяв точности язык, допускаемый НКА.Да. Так как для любого НКА существует эквивалентный ему ДКА. А множество языков,задаваемых ДКА, совпадает со множеством языков, задаваемых РВ.1.2 Верно ли, что для всякого регулярного языка существует принимающий его ДКА сединственным финальным состоянием?Нет.
S → aA | b | ε ; A → α . Данный ДКА минимален и имеет 2 фин. Состояния.1.3 Верно ли, что для всякого регулярного языка существует принимающий его НКА сединственным финальным состоянием?Да. Построить какой-либо НКА для регулярного языка всегда возможно.2.1 Верно ли, что для конечных языков лемма о возрастании регулярных выраженийнеприменима?Нет. Любой конечный язык является регулярным, И в условии леммы требуется w ∀i > 0следовательно язык должен быть бесконечным. Лемма не работает.2.2 Пусть M 1 = {полный жованый крот}.
Автомат M 2 получается из автомата M 1 путём заменымножества финальных состояний его дополнением. Верно ли что L( M 2 ) = L( M 1 ) ?Да. (Построим ДКА, I( M 1 ).2.3 Существует ли детерминированная машина Тьюринга, распознающая язык {a b , n > 0} ?n nДа. Строим её. Далее -- ( g 0 , λ ) → Accept ;( g 2 , λ ) → Accept .
Останов, если нет ничего,что можно было бы удалить процедурой справа. Если совсем ничего не осталось – разбор законч.3.1 Верно ли, что если два минимальных конечных автомата содержат равное количествосостояний, то они распознают разные языки.Да. Потому что для эквивалентных языков минимальные ДКА совпадают. (Допустим, чтоэто не так, но если min DKA1 ( L) < min DKA2 ( L) , то min DKA2 -- не является минимальнымпротиворечиеколичество состояний одинаковое.3.2* Верно ли, что если для конечного языка выполняется лемма о разрастании, то не являетсярегулярным? Да.3.3* Верно ли, что объединение двух нерегулярных автоматов, всегда нерегулярно? Нет?!4.1 Верно ли, что МП автомат не являющийся детерминированным, может не иметь ε-переходов?Да. Т.к.
если у него будут два состояния D обозначать разные переходы, то он уже не будетНМП.4.2 Верно ли, что КС-грамматика без eps-правил, порождающая язык L = {a | ε } не существует?Нет. S->a|eps. Т.е. в КС-грамматике без эпс. не допускается правило S->eps., если S неприсутствует в первых частях других правил.4.3 Верно ли, что любой КС-язык можно задать МП-автоматом ровно с одним состоянием?Да. A → a : D(g, λ , A) → (g, a) | a : D ( g , a, α ) → ( g , λ ) .
Плюс расписать всесоставляющие M G .5.1 Пусть L1 -- язык, не являющийся контекстно-свободным, а L2 -- контекстно-свободный язык,не являющийся регулярным. Вытекает ли из этих посылок, что L1L2 также не является регулярнымязыком?Да. Регулярный язык является регулярным множеством. Есть свойство, что для двухрегулярных множеств P и Q, P ∪ Q -- регулярное множество, PQ -- регулярное множество, P* -регулярное. И никакое другое множеств не является регулярным. Да, вытекает -- L1L2 не регул.язык.5.2 Верно ли, что любая регулярная грамматика является LL(1) грамматикой?Нет. Если в грамматике есть факторизация или левая рекурсия, то она не является LL(1).5.3 Пусть M = {полный жованый крот}. Верно ли что M удовлетворяет определениюдетерминированного МП-автомата?Да.
Выполняются оба требуемых условия (по определению) – возможность перехода изD( g , t , z ) и D( g , eps, z) ≠ ∅, ⇒ D( g , a, z) = ∅ .6.1* Верно ли утверждение, что если грамматика является LR(3) грамматикой, то она являетсяоднозначной грамматикой?При LR-разборе возможны конфликты свёртка/свёртка и сдвиг/свёртка. Если дляизбежания конфликта требуется авансцепочка > 3, то грамматика не LR(3). То же самое, если естьконфликты при авансцепочке=3.Значит для грамматики верно, что у нее нет конфликтов – дерево разбора единственно.Однозначная грамматика – грамматика, для любой терминальной цепочки в которой ∃! дереворазбора.6.2 Верно ли, что при построении LR(0) анализатора могут возникнуть конфликты shift/shift?Нет, могут быть лишь конфликты shift/reduce, reduce/reduce.6.3* Верно ли, что если для любых натуральных k, n > 1000 в языке L найдётся слово a=xyuvz,причем |w|>k, |uv|>0, |uyv|<=n, и xu1000yv1000z ∉ L, то язык L не является контекстносвободным? Нет.составляющие M G .что можно было бы удалить процедурой справа.
Если совсем ничего не осталось – разбор законч.3.1 Верно ли, что если два минимальных конечных автомата содержат равное количествосостояний, то они распознают разные языки.Да. Потому что для эквивалентных языков минимальные ДКА совпадают. (Допустим, чтоэто не так, но если min DKA1 ( L) < min DKA2 ( L) , то min DKA2 -- не является минимальнымпротиворечиеколичество состояний одинаковое.3.2* Верно ли, что если для конечного языка выполняется лемма о разрастании, то не являетсярегулярным? Да.3.3* Верно ли, что объединение двух нерегулярных автоматов, всегда нерегулярно? Нет?!4.1 Верно ли, что МП автомат не являющийся детерминированным, может не иметь ε-переходов?Да. Т.к.
если у него будут два состояния D обозначать разные переходы, то он уже не будетНМП.4.2 Верно ли, что КС-грамматика без eps-правил, порождающая язык L = {a | ε } не существует?Нет. S->a|eps. Т.е. в КС-грамматике без эпс. не допускается правило S->eps., если S неприсутствует в первых частях других правил.4.3 Верно ли, что любой КС-язык можно задать МП-автоматом ровно с одним состоянием?Да.
A → a : D (g, λ , A) → (g, a) | a : D( g , a, α ) → ( g , λ ) . Плюс расписать всеДа. Строим её. Далее -- ( g 0 , λ ) → Accept ;( g 2 , λ ) → Accept . Останов, если нет ничего,2.3 Существует ли детерминированная машина Тьюринга, распознающая язык {a nb n , n > 0} ?Да. (Построим ДКА, I( M 1 ).множества финальных состояний его дополнением. Верно ли что L ( M 2 ) = L( M 1 ) ?1.1 Верно ли, что для всякого НКА существует однозначная регулярная грамматика, порождающаяв точности язык, допускаемый НКА.Да. Так как для любого НКА существует эквивалентный ему ДКА. А множество языков,задаваемых ДКА, совпадает со множеством языков, задаваемых РВ.1.2 Верно ли, что для всякого регулярного языка существует принимающий его ДКА сединственным финальным состоянием?Нет. S → aA | b | ε ; A → α .
Данный ДКА минимален и имеет 2 фин. Состояния.1.3 Верно ли, что для всякого регулярного языка существует принимающий его НКА сединственным финальным состоянием?Да. Построить какой-либо НКА для регулярного языка всегда возможно.2.1 Верно ли, что для конечных языков лемма о возрастании регулярных выраженийнеприменима?Нет. Любой конечный язык является регулярным, И в условии леммы требуется w ∀i > 0следовательно язык должен быть бесконечным.
Лемма не работает.2.2 Пусть M 1 = {полный жованый крот}. Автомат M 2 получается из автомата M 1 путём заменыТеория 2013, 3 варианта, ответы с фоток у которых ‘+’.* = не точно. Если есть ещё фотки – присылайте на roman@dovgopol.com, обновлюЕсли не нашли свой вопрос здесь – пишем «Да, по определению». Серьёзно.6.1* Верно ли утверждение, что если грамматика является LR(3) грамматикой, то она являетсяоднозначной грамматикой?При LR-разборе возможны конфликты свёртка/свёртка и сдвиг/свёртка.
Если дляизбежания конфликта требуется авансцепочка > 3, то грамматика не LR(3). То же самое, если естьконфликты при авансцепочке=3.Значит для грамматики верно, что у нее нет конфликтов – дерево разбора единственно.Однозначная грамматика – грамматика, для любой терминальной цепочки в которой ∃! дереворазбора.6.2 Верно ли, что при построении LR(0) анализатора могут возникнуть конфликты shift/shift?Нет, могут быть лишь конфликты shift/reduce, reduce/reduce.6.3* Верно ли, что если для любых натуральных k, n > 1000 в языке L найдётся слово a=xyuvz,причем |w|>k, |uv|>0, |uyv|<=n, и xu1000yv1000z ∉ L, то язык L не является контекстносвободным? Нет.язык.5.2 Верно ли, что любая регулярная грамматика является LL(1) грамматикой?Нет.
Если в грамматике есть факторизация или левая рекурсия, то она не является LL(1).5.3 Пусть M = {полный жованый крот}. Верно ли что M удовлетворяет определениюдетерминированного МП-автомата?Да. Выполняются оба требуемых условия (по определению) – возможность перехода изD( g , t, z) и D( g , eps, z) ≠ ∅, ⇒ D( g , a, z) = ∅ .регулярное. И никакое другое множеств не является регулярным. Да, вытекает -- L1L2 не регул.языком?Да. Регулярный язык является регулярным множеством. Есть свойство, что для двухрегулярных множеств P и Q, P ∪ Q -- регулярное множество, PQ -- регулярное множество, P * --не являющийся регулярным. Вытекает ли из этих посылок, что L1L2 также не является регулярным5.1 Пусть L1 -- язык, не являющийся контекстно-свободным, а L2 -- контекстно-свободный язык,.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
