Множество всех цепочек в алфавите A

 

Обращение цепочки a обозначается как aR.

Итерация цепочки a n раз обозначается как an.

Какие из перечисленных ниже тождеств являются истинными для двух произвольных цепочек символов a и b, а какие нет:

|ab| = |a| + |b| = |ba|

|aR| = |a|

 (a2b2)R = (bR)2(aR)2

 

Кто (или что) для любого языка программирования выступает в роли генератора цепочек языка?

 грамматика

 

Операцией, которая определяется свойствами:

ea = ae = a,

<a1,...,an> <b1,...,bm> = <a1,...,an,b1,...,bm>, где аi, bi – символы; e – пустая цепочка символов

называется:

Конкатенацией

 

Языком L над алфавитом A называется:

Любое множество цепочек в алфавите A

 

Любое множество цепочек в алфавите A, называется

 языком

 

Операция над языками, которая определяется следующей формулой:

LM = {ab | a ∈ L, b ∈ M},

L0 = e, Ln+1 =LnL, называется

 произведение

 

 

Если язык конечен или образуется из конечных языков с помощью операций объединения, произведения и итерации, он называется

Регулярным

 

Отдельные конструкции в языках программирования являются регулярными языками. Как правило, это:

Идентификаторы

Числа

 

Грамматика I = L{L | D} , где L = {a,...,z}, D = {0,1,2,...,9} определяет множество:

 Идентификаторов

 

Какой язык порождается КС-грамматикой с правилами S  aSb, S  .

{ aⁿbⁿ | n  0}

 

Грамматика R = SNFP, где S = {+,-,e}, N = DD*, F = .N | e , P = eSN | e определяет множество:

Чисел

 

Грамматика I = D{ D} , где D = {0,1,2,...,9} определяет множество:

Целых чисел без знака

 

Пусть, множество всех языков над алфавитом A обозначено Langs(A).

Выражение, построенное из конечных языков, принадлежащих Langs(A), и переменных с помощью операций объединения, произведения и итерации называется:

Регулярным

 

Набор G = (N,T,P,S), где

N – алфавит нетерминальных символов; T – алфавит терминальных символов, P – конечное множество правил (или продукций); правило имеет вид a → b, где a, b ∈ (T U N)*, причем a содержит хоть один нетерминальный символ;

S – начальный нетерминальный символ, S ∈ N.

называется:

Грамматикой

 

По классификации Н. Хомского,

грамматика с правилами вида a → b, где |a | <= |b |. относится к типу:

 1

 

По классификации Н. Хомского, контекстно-свободной называется грамматика с правилами вида:

A → a, где A ∈ VN, a ∈ V*

 

По классификации Н. Хомского,

грамматика с правилами вида A → a, где A ∈ N, a ∈ V* относится к типу:

2

                                                                                                         4. 3

По классификации Н. Хомского,

грамматика с правилами вида A → UT | e, где A, U ∈ VN, T ∈ VT относится к типу:

3

Дерево следующего вида:

корнем является нетерминальный символ;

вершинами являются символы из V;

если вершина A имеет непосредственных потомков X1, ..., Xn (или e), то в грамматике есть правило A → X1...Xn (или A → e). Порядок потомков совпадает с порядком символов в правиле, называется:

деревом вывода

КС-грамматика G такая, что у каждой цепочки языка L(G) имеется только одно дерево вывода, называется:

Однозначной

 

Анализ, задачей которого является проверка, принадлежит ли произвольная заданная цепочка a ∈ T * языку L(G) для заданной грамматики G, называется:

Синтаксическим

 

Грамматика G = (N,T,P,S) и автомат A = (Q,T,t,q0,F) называются соответствующими друг другу, если:

N = Q, S = q0, X → aY ∈ P Ы (X,a) →Y ∈ t, X → e ∈ P Ы X ∈ F

 

Конечный автомат представленный диаграммой:

 

 

позволяет распознавать:

Числа

 

Конечный автомат представленный диаграммой:

 

 

позволяет распознавать:

Идентификаторы

 

Недетерминированный автомат, изображенный на следующем рисунке, 

 

имеет грамматику с правилами:

q0 → aq1 | bq2, q1 → aq1 | aq3 | bq1 | bq2, q2 → aq1 | aq2 | bq2 | bq3, q3 → aq3 | bq3 | e

 

Для инфиксного выражения a+b*c-(d+e) правильной польской суффиксной записью будет:

abc*de+-+

 

Какая синтаксическая конструкция описывается следующей диаграммой:

Объявление массива

 

Магазинные автоматы или автоматы с магазинной памятью – МП-автоматы, являются формальной моделью:

⇐ Предыдущая12345Следующая ⇒

Поделиться: