Теория формальных языков, грамматик и автоматов. Ишакова Е.Н. - 7 стр.

UptoLike

ВУЗ: 

ОГУ | Оренбург

Составители: 

Рубрика: 

7
3) CB → BC; 4) cC → cc;
5) BB → bb.
в) Контекстно-свободный язык L(G)={(ab)
n
(cb)
n
| n>0 } определяется
грамматикой с правилами вывода:
1) S → aQb | accb;
2) Q → cSc.
г) Регулярный язык L(G)={
ω
⊥ |
ω
∈{a, b}
+
, где нет двух рядом стоящих а}
определяется грамматикой с правилами вывода:
1) S → A⊥ | B⊥;
2) A → a | Ba;
3) B → b | Bb | Ab.
Постановка задачи к лабораторной работе № 1
При выполнении лабораторной работы следует реализовать следующие
действия:
1) составить грамматику, порождающую формальный язык, заданный в
соответствии с вариантом;
2) определить тип формальной грамматики и языка по классификации
Хомского;
3) разработать программное средство, распознающее тип введенной поль-
зователем грамматики по классификации Хомского.
Варианты индивидуальных заданий представлены в таблице 1.1.
Таблица 1.1 – Варианты индивидуальных заданий к лабораторной работе № 1
Вариант Формальный язык
1 L(G)={a
n
b
m
c
k
| n, m, k>0}
2
L(G)={(ab)
n
(cb)
m
| n, m≥0}
3
L(G)={0
n
(10)
m
| n, m≥0}
4
L(G)={wcwcw | w∈{a, b}
+
}
5 L(G)={c
2n
d
n
| n>0}
6
L(G)={l+l-l | l ∈{a, b}
+
}
7 L(G)={(10)
n-1
(01)
n+1
| n>0}
8
L(G)={(ac)
n
| n>0, a∈{b, d}, c∈{+, -}}
9
L(G)={⊥(010)
n
⊥
| n>0}
10
L(G)={a
1
a
2
…a
n
a
n
…a
2
a
1
| a
i
∈{0, 1}}
11
L(G)={a
1
a
2
…a
n
a
1
a
2
…a
n
| a
i
∈{c, d}}
12
L(G)={ab.b | a
i
∈{+, -}, b∈{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
+
} 
                   3) CB → BC;                      4) cC → cc;
     5) BB → bb.
     в) Контекстно-свободный язык L(G)={(ab)n(cb)n | n>0 } определяется
грамматикой с правилами вывода:
     1) S → aQb | accb;
     2) Q → cSc.
     г) Регулярный язык L(G)={ω⊥ | ω∈{a, b}+, где нет двух рядом стоящих а}
определяется грамматикой с правилами вывода:
     1) S → A⊥ | B⊥;
     2) A → a | Ba;
     3) B → b | Bb | Ab.

               Постановка задачи к лабораторной работе № 1
      При выполнении лабораторной работы следует реализовать следующие
действия:
      1) составить грамматику, порождающую формальный язык, заданный в
соответствии с вариантом;
      2) определить тип формальной грамматики и языка по классификации
Хомского;
      3) разработать программное средство, распознающее тип введенной поль-
зователем грамматики по классификации Хомского.
      Варианты индивидуальных заданий представлены в таблице 1.1.

  Таблица 1.1 – Варианты индивидуальных заданий к лабораторной работе № 1

  Вариант                             Формальный язык
                            n m k
     1             L(G)={a b c | n, m, k>0}
     2             L(G)={(ab)n(cb)m | n, m≥0}
     3             L(G)={0n(10)m | n, m≥0}
     4             L(G)={wcwcw | w∈{a, b}+}
     5             L(G)={c2ndn | n>0}
     6             L(G)={l+l-l | l ∈{a, b}+}
     7             L(G)={(10)n-1(01)n+1 | n>0}
     8             L(G)={(ac)n | n>0, a∈{b, d}, c∈{+, -}}
     9             L(G)={⊥(010)n⊥ | n>0}
     10            L(G)={a1a2…anan…a2a1 | ai∈{0, 1}}
     11            L(G)={a1a2…ana1a2…an | ai∈{c, d}}
     12            L(G)={ab.b | ai∈{+, -}, b∈{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}+}


                                                                                7

Страницы