Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Лабораторная работа №1
а) разработать программное средство, распознающее тип введенной пользователем грамматики по классификации Хомского;
б) вывести десять слов языка, порождаемого грамматикой;
в) описать язык, порождаемый грамматикой.
Правила грамматики:
|
Решение
Программа, распознающая тип введённой пользователем грамматики, была написана на языке Python. Программный код, реализующий алгоритм определения типа грамматики, приведён ниже.
from math import *
lev=['S','S','K','KS','K']
prav=['ab','aKSb','bSb','b','e']
for i in range(len(lev)):
if len(lev[i])<=len(prav[i]):
kz=kz+1
if len(lev[i])==1 and ord(lev[i])<97 and ord(lev[i])>64:
ks=ks+1
s=0
for j in prav[i]:
if ord(j)>64 and ord(j)<97 or ord(j)==101:
s=s+1
if s==1:
l=l+1
k=prav[i]
if ord(k[-1])<97 and ord(k[-1])>64 or ord(j)==101 :
pl=pl+1
if kz==(len(lev)) and ks==(len(lev)) and l==(len(lev)) and pl==(len(lev)):
print('праволинейная грамматика')
if kz==(len(lev)) and ks==(len(lev)) and l==(len(lev)) and pl<(len(lev)):
print('линейная грамматика')
if kz==(len(lev)) and ks==(len(lev)) and l<(len(lev)) and pl<(len(lev)):
print('контекстно-свободная грамматика')
if kz==(len(lev)) and ks<(len(lev)) and l<(len(lev)) and pl<(len(lev)):
print('контектно-зависимая грамматика')
if kz<(len(lev)) and ks<(len(lev)) and l<(len(lev)) and pl<(len(lev)):
print('грамматика общего вида') Результат работы программы:
Грамматика общего вида. Вывод нескольких её слов:
Язык с заданными правилами грамматики не описывается однозначным образом
Лабораторная работа №2
Задание:
Разработать программное средство, реализующее следующие функции:
Правила грамматики:
S→bS, J→bW, S→aJ, J→aJ, W→aS, W→bJ, W→aW, W→ε
Решение
Для решения задач, поставленных в работе, была написана программа на языке Python.
from math import *
lev=['S','J','S','J','W','W','W','W']
prav=['bS','bW','aJ','aJ','aS','bJ','aW','e']
Q=[]
E=[]
Y=[]
I=[]
F=[]
P=[]
N=[]
B=[]
pl=0
kz=0
ks=0
l=0
for i in range(len(lev)):
if len(lev[i])<=len(prav[i]):
kz=kz+1
if len(lev[i])==1 and ord(lev[i])<97 and ord(lev[i])>64:
ks=ks+1
s=0
for j in prav[i]:
if ord(j)>64 and ord(j)<97 or ord(j)==101:
s=s+1
if s==1:
l=l+1
k=prav[i]
if ord(k[-1])<97 and ord(k[-1])>64 or ord(j)==101 :
pl=pl+1
if kz==(len(lev)) and ks==(len(lev)) and l==(len(lev)) and pl==(len(lev)):
print('праволинейная грамматика')
if kz==(len(lev)) and ks==(len(lev)) and l==(len(lev)) and pl<(len(lev)):
print('линейная грамматика')
if kz==(len(lev)) and ks==(len(lev)) and l<(len(lev)) and pl<(len(lev)):
print('контекстно-свободная грамматика')
if kz==(len(lev)) and ks<(len(lev)) and l<(len(lev)) and pl<(len(lev)):
print('контектно-зависимая грамматика')
if kz<(len(lev)) and ks<(len(lev)) and l<(len(lev)) and pl<(len(lev)):
print('грамматика общего вида')
for i in range(len(lev)):
for j in lev:
s=0
for w in range(len(Q)):
if j!=Q[w]:
s=s+1
if s==len(Q):
Q.append(j)
for i in range(len(lev)):
for j in prav[i]:
s=0
if ord(j)>96 and ord(j)<124 and ord(j)!=101:
for w in range(len(E)):
if j!=E[w]:
s=s+1
if s==len(E):
E.append(j)
for i in range(len(lev)):
for j in prav[i]:
s=0
if ord(j)==101:
for w in range(len(F)):
if j!=F[w]:
s=s+1
if s==len(F):
F.append(lev[i])
I.append(lev[0])
for i in range(len(lev)-len(F)):
R=lev[i]+prav[i]
Y.append(R)
print(Q)
print(E)
print(F)
print(I)
print(Y)
p=0
for i in range(len(Q)):
P=[]
R=Q[i]
s=0
z=0
U=E
for j in range(len(Y)):
for k in range(len(Y[j])):
if k==1 and Y[j][0]==R:
s=s+1
if k==2 and Y[j][0]==R:
P.append(Y[j][1])
for t in range(len(U)):
u=U[t]
P.remove(u)
if len(P)!=0:
print('автомат недетерминированный')
else:
p=p+1
if p==len(Q):
print('автомат полный детерминированный')
Для заданной в работе грамматики программа выдает результат
>>> праволинейная грамматика
['S', 'J', 'W']
['b', 'a']
['W']
['S']
['SbS', 'JbW', 'SaJ', 'JaJ', 'WaS', 'WbJ', 'WaW']
автомат недетерминированный
Получили, что автомат недетерминирован. Преобразуем его к детерминированному виду. Представим автомат в виде схемы.
С её помощью составим табл. В её первой строке приведены все подмножества множества состояний, а во второй и третьей – состояния достижимые из данных подмножеств по переходам a и b, соответственно.
|
S |
J |
W |
SJ |
SW |
JW |
SJW |
|
|
a |
J |
J |
WS |
J |
SJW |
WSJ |
WSJ |
|
b |
S |
W |
J |
SW |
SJ |
JW |
WSJ |
.
Лабораторная работа №3
Минимизация полных детерминированных
конечных автоматов
Задание:
Разработать программное средство, реализующее следующие функции:
.
Решение
Определение принадлежности заданного конечного автомата к классу полных детерминированных конечных автоматов и процедура минимизации автоматов из этого класса были реализованы в виде программы на языке Python. Текст программы приведён ниже.
from math import *
lev=['A','A','B','B','C','C','D','D','E','E','F','F','G','G','E','G']
prav=['aB','bA','aC','bE','bE','aC','aB','bG','aG','bC','bD','aG','aE','bD','e','e']
Q=[]
E=[]
Y=[]
I=[]
F=[]
P=[]
N=[]
B=[]
pl=0
kz=0
ks=0
l=0
for i in range(len(lev)):
if len(lev[i])<=len(prav[i]):
kz=kz+1
if len(lev[i])==1 and ord(lev[i])<97 and ord(lev[i])>64:
ks=ks+1
s=0
for j in prav[i]:
if ord(j)>64 and ord(j)<97 or ord(j)==101:
s=s+1
if s==1:
l=l+1
k=prav[i]
if ord(k[-1])<97 and ord(k[-1])>64 or ord(j)==101 :
pl=pl+1
if kz==(len(lev)) and ks==(len(lev)) and l==(len(lev)) and pl==(len(lev)):
print('праволинейная грамматика')
if kz==(len(lev)) and ks==(len(lev)) and l==(len(lev)) and pl<(len(lev)):
print('линейная грамматика')
if kz==(len(lev)) and ks==(len(lev)) and l<(len(lev)) and pl<(len(lev)):
print('контекстно-свободная грамматика')
if kz==(len(lev)) and ks<(len(lev)) and l<(len(lev)) and pl<(len(lev)):
print('контектно-зависимая грамматика')
if kz<(len(lev)) and ks<(len(lev)) and l<(len(lev)) and pl<(len(lev)):
print('грамматика общего вида')
for i in range(len(lev)):
for j in lev:
s=0
for w in range(len(Q)):
if j!=Q[w]:
s=s+1
if s==len(Q):
Q.append(j)
for i in range(len(lev)):
for j in prav[i]:
s=0
if ord(j)>96 and ord(j)<124 and ord(j)!=101:
for w in range(len(E)):
if j!=E[w]:
s=s+1
if s==len(E):
E.append(j)
for i in range(len(lev)):
for j in prav[i]:
s=0
if ord(j)==101:
for w in range(len(F)):
if j!=F[w]:
s=s+1
if s==len(F):
F.append(lev[i])
I.append(lev[0])
for i in range(len(lev)-len(F)):
R=lev[i]+prav[i]
Y.append(R)
print(Q)
print(E)
print(F)
print(I)
print(Y)
p=0
for i in range(len(Q)):
P=[]
R=Q[i]
s=0
z=0
U=E
for j in range(len(Y)):
for k in range(len(Y[j])):
if k==1 and Y[j][0]==R:
s=s+1
if k==2 and Y[j][0]==R:
P.append(Y[j][1])
for t in range(len(U)):
u=U[t]
P.remove(u)
if len(P)!=0:
print('автомат недетерминированный')
else:
p=p+1
if p==len(Q):
print('автомат полный детерминированный')
for i in range(len(Q)):
r=0
for j in range(len(Y)):
k=Y[j]
if k[-1]==Q[i]:
r=r+1
N.append(r)
print(N)
for i in range(len(Y)):
k=Y[i]
for j in range(len(N)):
if N[j]==0:
if k[0]==Q[j]:
B.append(i)
for i in range(len(B)):
Y.remove(Y[B[i]])
if i==0:
B[i+1]=B[i+1]-1
print(B)
print(Y)
for i in range(len(N)):
if N[i]==0:
Q.remove(Q[i])
L=[]
for j in range(len(Q)):
t=0
for i in F:
if Q[j]==i:
t=t+1
if t==0:
L.append(Q[j])
n=len(Q)
P=[0]*n
for i in range(n):
P[i]=[0]*n
P[0][0]=L
P[0][1]=F
G=[0]*n
m=len(E)+2
for i in range(n):
G[i]=[0]*m
G1=[0]*n
for i in range(n):
G1[i]=[0]*3
for i in range(n):
G1[i][0]=Q[i]
for j in range(len(Y)):
k=Y[j]
if k[0]==G1[i][0] and k[1]=='a':
G1[i][1]=k[-1]
if k[0]==G1[i][0] and k[1]=='b':
G1[i][2]=k[-1]
for g in range(n-1):#главный цикл
for i in range (n):
G[i][0]=Q[i]
l=0
for q in range(n):
if P[g][q]!=0:
l=l+1
for j in range(l):
for k in P[g][j]:
if G[i][0]==k:
G[i][1]=j
if G[i][0]==G1[i][0] and G1[i][1]==k:
G[i][2]=j
if G[i][0]==G1[i][0] and G1[i][-1]==k:
G[i][3]=j #сформирована главная матрица
P[g+1][0]=Q[0]
mn=1
c4=0
nep=0
for j in range(l):
for k in P[g][j]:
for h in range(n): # поиск нужного столбца в главной матрице
if G[h][0]==k: # поиск нужного столбца в главной матрице
h1=h # поиск нужного столбца в главной матрице
for j1 in range(mn):
for k1 in P[g+1][j1]:
for h in range(n): # поиск нужного столбца в главной матрице
if G[h][0]==k1: # поиск нужного столбца в главной матрице
h2=h # поиск нужного столбца в главной матрице
c4=c4+1
if k!=k1 and G[h1][1]==G[h2][1] and G[h1][2]==G[h2][2] and G[h1][3]==G[h2][3] and k!=0: # нужный столбец совпадает с исходным то добваляем букву к множеству
P[g+1][j1]=P[g+1][j1]+k
break
if k!=k1 and (G[h1][1]!=G[h2][1] or G[h1][2]!=G[h2][2] or G[h1][3]!=G[h2][3]) and k!=0: #сколько раз неподошло
nep=nep+1 #неподходит множеству
if nep==c4: # если никакому не подошед, добавляем новое множество
P[g+1][mn]=k
mn=mn+1
c4=0
nep=0
print(P[n-1])
print(G)
Q1=[]
for i in range(n):
if P[n-1][i]!=0:
Q1.append(P[n-1][i])
print(Q1)
print(E)
F1=[]
for i in range(n):
if P[n-1][i]!=0:
for k in F:
for j in P[n-1][i]:
if j==k:
F1.append(P[n-1][i])
break
print(F1)
I1=[]
for i in range(n):
if P[n-1][i]!=0:
for k in I:
for j in P[n-1][i]:
if j==k:
I1.append(P[n-1][i])
break
print(I1)
Y1=[]
for i in range(n):
if P[n-1][i]!=0:
for k in range(len(G)):
g=G[k]
for j in P[n-1][i]:
if j==g[0]:
R=P[n-1][i]+'a'+P[n-1][g[2]]
R1=P[n-1][i]+'b'+P[n-1][g[3]]
Y1.append(R)
Y1.append(R1)
break
print(Y1)Результат работы программы приведён на рисунке. Видим, что автомат полный детерминированный.
Его минимизированный аналог представлен ниже.
Таким образом, язык, распознаваемый заданным конечным автоматом, представим следующим регулярным выражением
b*a(a*b*)*