ÿþ2 . 2 . G r a m a t y k i , w y p r o w a d z e n i a
G r a m a t y k a
G r a m a t y k G n a z y w a m y c z w ó r k u p o r z d k o w a n
G = < N , T , P , Z >
g d z i e :
N z b i ó r s y m b o l i n i e t e r m i n a l n y c h ,
T z b i ó r s y m b o l i t e r m i n a l n y c h ,
P z b i ó r p r o d u k c j i , z k t ó r y c h k a |d a m a p o s t a ± ’! ²
Z " N w y r ó |n i o n y s y m b o l p o c z t k o w y ( n i e t e r m i n a l )
p r z y c z y m
P †" ( N *"T ) + × ( N *"T ) *
P = { ±’!² | ± " ( N *"T ) + , ² "( N *"T ) * }
W y p r o w a d z a l n o [
S Bo w o È j e s t w y p r o w a d z a l n e b e z p o [r e d n i o z e s Bo w a É w g r a m a t y c e G , c o z a p i s u j e m y
É Ò!G È
j e |e l i :
É = ³±´
È = ³²´
( ± ’! ²) " P
±, ², ³, ´, È, É " ( N *"T ) *
S Bo w o È j e s t w y p r o w a d z a l n e z e s Bo w a É w g r a m a t y c e G , c o z a p i s u j e m y
É Ò!G + È
j e |e l i i s t n i e j Æ0 , Æ1 , . . . , Æn " ( N *"T ) * t a k i e , |e :
Æ0 = É
Æn = È
Æi - 1 Ò!G Æi d l a i = 1 , 2 , . . . , n
S e k w e n c j Æ0 , Æ1 , . . . , Æn n a z y w a m y w y p r o w a d z e n i e m o d Bu g o [c i n .
D e f i n i u j e m y p o n a d t o :
( É Ò!G * È ) Ô! ( É Ò!G + È ) (" ( É = È )
R e l a c j e Ò!G + o r a z Ò!G * s o d p o w i e d n i o p r z e c h o d n i m o r a z p r z e c h o d n i m i z w r o t n y m
d o m k n i c i e m r e l a c j i b e z p o [r e d n i e j w y p r o w a d z a l n o [c i Ò!G . J e |e l i w i a d o m o , o j a k
g r a m a t y k c h o d z i , p o m i j a m y d o l n y i n d e k s G w o z n a c z e n i u t y c h r e l a c j i p i s z c p o p r o s t u :
Ò!+ , Ò!* o r a z Ò!.
J z y k g e n e r o w a n y p r z e z g r a m a t y k
G r a m a t y k a j e s t j e d n y m z e s p o s o b ó w d e f i n i o w a n i a j z y k a f o r m a l n e g o . M a j c d a n
g r a m a t y k G o z n a c z a m y p r z e z L ( G ) z b i ó r w s z y s t k i c h s Bó w , k t ó r e m o g b y w t e j
g r a m a t y c e w y p r o w a d z o n e z s y m b o l u p o c z t k o w e g o Z . Z b i ó r t e n n a z y w a m y j z y k i e m
g e n e r o w a n y m p r z e z d a n g r a m a t y k .
L ( G ) = { x " T * | Z Ò!G * x }
F o r m a z d a n i o w a
Aa Dc u c h x " ( N *"T ) * n a z y w a m y f o r m z d a n i o w g r a m a t y k i G , j e [l i m o |n a g o
w y p r o w a d z i z s y m b o l u p o c z t k o w e g o Z .
x " ( N *"T ) * j e s t f o r m z d a n i o w Ô! Z Ò!G * x
U w a g a : t e r m i n u s Bo w o u |y w a m y w r o z u m i e n i u Ba Dc u c h a z b u d o w a n e w y Bc z n i e z s y m b o l i
t e r m i n a l n y c h
x " T * j e s t s Bo w e m Ô! Z Ò!G * x
H i e r a r c h i a C h o m s k y e g o
N o a m C h o m s k y z d e f i n i o w a B c z t e r y k l a s y g r a m a t y k o r a z c z t e r y k l a s y j z y k ó w f o r m a l n y c h .
K l a s y t e n u m e r o w a n e s o d 0 d o 3 .
K l a s a 0
G r a m a t y k G = < N , T , P , Z > , w k t ó r e j p r o d u k c j e m a j p o s t a ± ’! ² , g d z i e ± i ² s
d o w o l n y m i Ba Dc u c h a m i s y m b o l i t e j g r a m a t y k i , p r z y c z y m ± `" µ n a z y w a m y
s e m i - g r a m a t y k a m i T h u e g o , g r a m a t y k a m i b e z o g r a n i c z e D, g r a m a t y k a m i s t r u k t u r f r a z o w y c h ,
g r a m a t y k a m i k o m b i n a t o r y c z n y m i l u b g r a m a t y k a m i k l a s y 0 .
D e f i n i c j a g r a m a t y k k l a s y 0 , j a k w i d a , n i e n a k Ba d a |a d n y c h o g r a n i c z e D n a p o s t a p r o d u k c j i
g r a m a t y k i w s t o s u n k u d o o g ó l n e j d e f i n i c j i g r a m a t y k i .
J z y k i g e n e r o w a n e p r z e z g r a m a t y k i t e g o t y p u n o s z n a z w j z y k ó w r e k u r e n c y j n i e
p r z e l i c z a l n y c h .
P r z e z G K O M B o z n a c z y m y k l a s g r a m a t y k k o m b i n a t o r y c z n y c h , a p r z e z L R P k l a s j z y k ó w
r e k u r e n c y j n i e p r z e l i c z a l n y c h .
F u n d a m e n t a l n y p r o b l e m , k t ó r y b d z i e p ó zn i e j n a s z y m g Bó w n y m p r z e d m i o t e m
z a i n t e r e s o w a n i a , m i a n o w i c i e : c z y s Bo w o x n a l e |y d o j z y k a g e n e r o w a n e g o p r z e z d a n
g r a m a t y k , j e s t n i e r o z s t r z y g a l n y d l a j z y k ó w g e n e r o w a n y c h p r z e z g r a m a t y k i
k o m b i n a t o r y c z n e . T e r m i n p r o b l e m w u p r o s z c z e n i u o z n a c z a p y t a n i e z w i z a n e z j a k i m [
w y s t p i e n i e m p e w n y c h o b i e k t ó w z p e w n y c h k l a s ( u n a s t y m i o b i e k t a m i s d o w o l n e
g r a m a t y k i p e w n e g o t y p u o r a z d o w o l n e s Bo w a n a d a l f a b e t e m d e f i n i o w a n y m p r z e z t e
g r a m a t y k i , z a [ w y s t p i e n i e m o b i e k t u b d z i e k o n k r e t n e s Bo w o i k o n k r e t n a g r a m a t y k a ) , n a
k t ó r e t o p y t a n i a m o |n a u d z i e l i o d p o w i e d z i : T A K l u b N I E . T e r m i n n i e r o z s t r z y g a l n y w
u p r o s z c z e n i u z n a c z y t y l e : n i e i s t n i e j e j e d n o z n a c z n y d e t e r m i n i s t y c z n y a l g o r y t m , k t ó r y d l a
k a |d e g o w y s t p i e n i a d a n e g o p r o b l e m u w s k o Dc z o n e j l i c z b i e k r o k ó w d a Bb y o d p o w i e d z T A K ,
j e |e l i p o p r a w n a o d p o w i e d z n a p y t a n i e z w i z a n e z w y s t p i e n i e m r o z w a |a n e g o p r o b l e m u
b r z m i T A K , o r a z N I E , g d y p o p r a w n a o d p o w i e d z b r z m i N I E . T e r m i n r o z s t r z y g a l n y w
u p r o s z c z e n i u z n a c z y t y l e : i s t n i e j e j e d n o z n a c z n y d e t e r m i n i s t y c z n y a l g o r y t m , k t ó r y d l a
k a |d e g o w y s t p i e n i a d a n e g o p r o b l e m u w s k o Dc z o n e j l i c z b i e k r o k ó w d a Bb y o d p o w i e d z T A K ,
j e |e l i p o p r a w n a o d p o w i e d z n a p y t a n i e z w i z a n e z w y s t p i e n i e m r o z w a |a n e g o p r o b l e m u
b r z m i T A K , o r a z N I E , g d y p o p r a w n a o d p o w i e d z b r z m i N I E .
P r o b l e m : c z y x " L ( G ) j e s t n i e r o z s t r z y g a l n y d l a G " G K O M B .
K l a s a 1
G r a m a t y k G = < N , T , P , Z > , w k t ó r e j p r o d u k c j e m a j p o s t a ± ’! ² , g d z i e ± i ² s
t a k i m i Ba Dc u c h a m i s y m b o l i t e j g r a m a t y k i , |e Ba Dc u c h ² j e s t p r z y n a j m n i e j t a k d Bu g i j a k
Ba Dc u c h ± ( | ±| d" | ²| ) o r a z d o d a t k o w o d o p u s z c z o n a j e s t p r o d u k c j a Z ’! µ, j e [l i j z y k
z a w i e r a s Bo w o p u s t e , n a z y w a m y g r a m a t y k a m i k o n t e k s t o w y m i , g r a m a t y k a m i m o n o t o n i c z n y m ,
g r a m a t y k a m i n i e s k r a c a j c y m i l u b g r a m a t y k a m i k l a s y 1 . T e r m i n k o n t e k s t o w y p o c h o d z i
o d t e g o , |e d l a k a |d e j g r a m a t y k i m o n o t o n i c z n e j m o |n a z n a l e z r ó w n o w a |n j e j ( t z n .
g e n e r u j c t e n s a m j z y k ) g r a m a t y k , k t ó r e j p r o d u k c j e m a j p o s t a ±1 A ±2 ’! ±1 ²±2 g d z i e A
j e s t n i e t e r m i n a l e m ( A " N ) , z a [ ±1 , ±2 , ² s d o w o l n y m i Ba Dc u c h a m i s y m b o l i g r a m a t y k i , p r z y
c z y m ² `" µ. P r o d u k c j e o t e j p o s t a c i p o z w a l a j n a z a s t p i e n i e n i e t e r m i n a l a A Ba Dc u c h e m ²
t y l k o w l e w o s t r o n n y m k o n t e k [c i e ±1 i p r a w o s t r o n n y m k o n t e k [c i e ±2 .
J z y k i g e n e r o w a n e p r z e z g r a m a t y k i t e g o t y p u n o s z n a z w j z y k ó w k o n t e k s t o w y c h .
P r z e z G K o z n a c z y m y k l a s g r a m a t y k k o n t e k s t o w y c h , a p r z e z L K k l a s j z y k ó w
k o n t e k s t o w y c h .
P r o b l e m : c z y x " L ( G ) j e s t r o z s t r z y g a l n y d l a G " G K .
P o n a d t o :
G K ‚" G K O M B
L K ‚" L R P
K l a s a 2
G r a m a t y k G = < N , T , P , Z > , w k t ó r e j p r o d u k c j e m a j p o s t a A ’! ² , g d z i e A j e s t
n i e t e r m i n a l e m ( A " N ) , z a [ Ba Dc u c h ² j e s t d o w o l n y m Ba Dc u c h e m s y m b o l i t e j g r a m a t y k i
n a z y w a m y g r a m a t y k a m i b e z k o n t e k s t o w y m i l u b g r a m a t y k a m i k l a s y 2 . T e r m i n
b e z k o n t e k s t o w y p o c h o d z i o d t e g o , |e p r o d u k c j e t a k i e j g r a m a t y k i p o z w a l a j n a
b e z w a r u n k o w e ( b e z u w z g l d n i a n i a k o n t e k s t u ) z a s t p i e n i e n i e t e r m i n a l a A Ba Dc u c h e m ².
J z y k i g e n e r o w a n e p r z e z g r a m a t y k i t e g o t y p u n o s z n a z w j z y k ó w b e z k o n t e k s t o w y c h .
P r z e z G B K o z n a c z y m y k l a s g r a m a t y k k o n t e k s t o w y c h , a p r z e z L B K k l a s j z y k ó w
k o n t e k s t o w y c h .
P r o b l e m : c z y x " L ( G ) j e s t r o z s t r z y g a l n y d l a G " G B K .
P o n a d t o :
G B K ‚" G K ‚" G K O M B
L B K ‚" L K ‚" L R P
K l a s a g r a m a t y k b e z k o n t e k s t o w y c h j e s t c h y b a n a j w a |n i e j s z ( z n a s z e g o p u n k t u w i d z e n i a )
k l a s g r a m a t y k , g d y | z a p o m o c g r a m a t y k t e j k l a s y o p i s u j e s i s k Ba d n i w i k s z o [c i j z y k ó w
p r o g r a m o w a n i a .
K l a s a 3
G r a m a t y k G = < N , T , P , Z > , w k t ó r e j k a |d a p r o d u k c j a m a p o s t a A ’! x B l u b A ’! x
g d z i e A i B s n i e t e r m i n a l a m i ( A , B " N ) , z a [ Ba Dc u c h x j e s t d o w o l n y m Ba Dc u c h e m
s y m b o l i t e r m i n a l n y c h t e j g r a m a t y k i ( x " T * ) n a z y w a m y g r a m a t y k p r a w o s t r o n n i e l i n i o w .
G r a m a t y k G = < N , T , P , Z > , w k t ó r e j k a |d a p r o d u k c j a m a p o s t a A ’! B x l u b A ’! x
g d z i e A i B s n i e t e r m i n a l a m i ( A , B " N ) , z a [ Ba Dc u c h x j e s t d o w o l n y m Ba Dc u c h e m
s y m b o l i t e r m i n a l n y c h t e j g r a m a t y k i ( x " T * ) n a z y w a m y g r a m a t y k l e w o s t r o n n i e l i n i o w .
G r a m a t y k i p r a w o s t r o n n i e l i n i o w e i l e w o s t r o n n i e l i n i o w e n a z y w a m y g r a m a t y k a m i l i n i o w y m i ,
g r a m a t y k a m i r e g u l a r n y m i l u b g r a m a t y k a m i k l a s y 3 .
J z y k i g e n e r o w a n e p r z e z g r a m a t y k i t e g o t y p u n o s z n a z w j z y k ó w r e g u l a r n y c h .
P r z e z G R G o z n a c z y m y k l a s g r a m a t y k r e g u l a r n y c h , a p r z e z L R G k l a s j z y k ó w r e g u l a r n y c h .
P r o b l e m : c z y x " L ( G ) j e s t r o z s t r z y g a l n y d l a G " G R G .
P o n a d t o :
G R G ‚" G B K ‚" G K ‚" G K O M B
L R G ‚" L B K ‚" L K ‚" L R P
K l a s a g r a m a t y k r e g u l a r n y c h j e s t t a k |e b a r d z o w a |n ( z n a s z e g o p u n k t u w i d z e n i a ) k l a s
g r a m a t y k , g d y | z a p o m o c g r a m a t y k t e j k l a s y o p i s u j e s i s k Ba d n i w i k s z o [c i p o d s t a w o w y c h
e l e m e n t ó w l e k s y k a l n y c h ( s Bo w n i k o w y c h ) j z y k ó w p r o g r a m o w a n i a ( t a k i c h j a k i d e n t y f i k a t o r y ,
s t a Be n u m e r y c z n e , s t a Be t e k s t o w e , k o m e n t a r z e , o p e r a t o r y , i t d .
P r z y k Ba d :
R o z w a |y m y g r a m a t y k G = < N , T , P , Z > , w k t ó r e j :
N = { S , A , B , C , D , E , F , G }
T = { a , b , c }
P = {
S ’! A b C | a D | A E | a B c | a b c
A ’! a
B ’! b
b C ’! b c
D ’! b c
a E ’! a b F c G
F ’! µ
b c G ’! b c
}
Z = S
T a g r a m a t y k a j e s t g r a m a t y k k o m b i n a t o r y c z n ( k l a s y 0 w l e w y c h s t r o n a c h p r o d u k c j i
w y s t p u j d o w o l n e Ba Dc u c h y s y m b o l i , s d w i e p r o d u k c j e s k r a c a j c e ) i r ó w n o c z e [n i e n i e j e s t
g r a m a t y k |a d n e j w |s z e j k l a s y . J z y k p r z e z n i g e n e r o w a n y j e s t o c z y w i [c i e j z y k i e m
r e k u r e n c y j n i e p r z e l i c z a l n y m . Z b a d a j m y , j a k i e s Bo w a s g e n e r o w a n e p r z e z t g r a m a t y k .
S Ò! A b C Ò! a b C Ò!b c
S Ò! a D Ò! a b c
S Ò! A E Ò! a E Ò! a b F c G Ò! a b c G Ò! a b c
S Ò! a B c Ò! a b c
S Ò! a b c
W i d a , |e j e d y n y m s Bo w e m g e n e r o w a n y m p r z e z t g r a m a t y k j e s t a b c . D l a j z y k a
L = { a b c }
m o |n a z b u d o w a z n a c z n i e p r o s t s z g r a m a t y k G 1 = < N 1 , T , P 1 , Z > , w k t ó r e j :
N 1 = { S }
T = { a , b , c }
P 1 = { S ’! a b c }
Z = S
G r a m a t y k a G 1 n a l e |y d o k l a s y 3 g r a m a t y k r e g u l a r n y c h . P o n i e w a |
L = L ( G ) = L ( G 1 )
w i c j z y k L n a l e |y d o k l a s y j z y k ó w r e g u l a r n y c h , m i m o |e m o |e b y w y g e n e r o w a n y p r z e z
g r a m a t y k z n a c z n i e s z e r s z e j k l a s y ( g r a m a t y k b e z o g r a n i c z e D) .
U w a g a : z a w s z e i n t e r e s o w a n a s b d z i e n a j w |s z a k l a s a , d o k t ó r e j n a l e |y b a d a n y j z y k .
Wyszukiwarka
Podobne podstrony:
lower,urządzenia obiektowe automatyki,Moorelower,urządzenia obiektowe automatyki,zbiory regularnelower,urządzenia obiektowe automatyki,drzewa rozbiorulower,urządzenia obiektowe automatyki,Turinglower,urządzenia obiektowe automatyki,algorytmy parsingulower,urządzenia obiektowe automatyki,Przeksztalcenia automatówlower,urządzenia obiektowe automatyki,zbiorylower,urządzenia obiektowe automatyki,jezyki1d urządzenia obiektowe automatykimotoiler urzadzenie do automatycznego oliwienia lancuchow motorowerow i motocykliWykonywanie połączeń w urządzeniach precyzyjnych i układach automatyki przemysłowejmechanik automatyki przemyslowej i urzadzen precyzyjnychszafran,podstawy automatyki,elementy UAR obiektu12 Użytkowanie maszyn i urządzeń oraz obiektówOchrona przed przepięciami urządzeń pracujących w niewielkich obiektach budowlanych14 Instalowanie urządzeń automatykiinstrukcja bhp mycia i dezynfekcji pomieszczen urzadzen sprzetu i naczyn dla obiektow handlowychwięcej podobnych podstron