საჭიროა არადეტერმინისტული სახელმწიფო მანქანა მ = (ქ, თ, დ, ქ 0 , ფ) შექმენით დეტერმინისტული სასრული მდგომარეობის მანქანა მ = (Q", თ, დ", q" 0 , F"). მშენებარე ავტომატისთვის საწყისი მდგომარეობა არის საწყისი ავტომატის საწყისი მდგომარეობის ε-დახურვა. ε-დახურვა - მდგომარეობების ერთობლიობა, რომლებიც ხელმისაწვდომია მოცემულიდან ε-ზე გადასვლებით. გარდა ამისა, სანამ არის მდგომარეობები, რომლებშიც გადასვლები არ არის აგებული (გადასვლები ხდება სიმბოლოებით, რომელთა მეშვეობითაც გადასვლები თავდაპირველ ავტომატშია), თითოეული სიმბოლოსთვის, ე-დახურვა იმ მდგომარეობების სიმრავლისა, რომლებიც ხელმისაწვდომია განხილული მდგომარეობიდან. განხილულ სიმბოლოზე გადასვლით გამოითვლება. თუ მდგომარეობა, რომელიც შეესაბამება ნაპოვნი ნაკრების უკვე არსებობს, მაშინ იქ ემატება გადასვლა. თუ არა, ემატება ახალი მიღებული მდგომარეობა.

მაგალითი

ინიციალიზაცია

აღინიშნება საწყისი მდგომარეობის ε-დახურვის შესაბამისი მდგომარეობები. ეს სახელმწიფოები შეესაბამებიან სახელმწიფოს ამომავალი DKA.

პირველი გამეორება

არის გადასვლები ε-დახურვიდან NCA მდგომარეობებზე 3 და 10 (შესაბამისად ადა გ, შესაბამისად). მე-3 მდგომარეობისთვის, ε-დახურვა არის მდგომარეობების სიმრავლე (3, 4, 6), 10-სთვის - (10). მოდით აღვნიშნოთ ახალი DFA მდგომარეობები, რომლებიც შეესაბამება ამ კომპლექტებს ბდა C.

DKA სახელმწიფო	NFA შტატების ნაკრები
		ა	ბ	გ
ა	{1, 2, 9}	ბ	-	C
ბ	{3, 4, 6}	-	-	-
C	{10}	-	-	-

მეორე გამეორება

NFA-ს მდგომარეობების სიმრავლიდან (3, 4, 6), რომელიც შეესაბამება DFA-ს მდგომარეობას ბარსებობს ორი გადასვლა - მდგომარეობა 5 (by ბ) და 7 (მით გ). მათი ε-დახურვები იკვეთება, მაგრამ თავად კომპლექტები განსხვავებულია, ამიტომ მათ ენიჭებათ ორი ახალი DFA მდგომარეობა - დდა ე. NFA-ს ქვეყნებიდან, რომლებიც შეესაბამება DFA-ს მდგომარეობას C, გადასვლები არ არის.

DKA სახელმწიფო	NFA შტატების ნაკრები	ხტუნვადი პერსონაჟები
		ა	ბ	გ
ა	{1, 2, 9}	ბ	-	C
ბ	{3, 4, 6}	-	დ	ე
C	{10}	-	-	-
დ	{2, 5, 8, 9}	-	-	-
ე	{2, 7, 8, 9}	-	-	-

მესამე გამეორება

NFA-ს სახელმწიფოების კომპლექტიდან, რომლებიც შეესაბამება DFA-ს ქვეყნებს დდა ეგადასვლები ხდება არსებული მდგომარეობების შესაბამისი მდგომარეობების სიმრავლეებზე (მდგომარეობის შესაბამისი სიმრავლიდან (2, 5, 8, 9) დ, ზე აგადასვლა მე-3 მდგომარეობაზე, რომელიც ეკუთვნის კომპლექტს (3, 4, 6), რომელიც შეესაბამება DFA მდგომარეობას ბ, ზე გ- სახელმწიფოს შესაბამისი მე-10 მდგომარეობაზე გადასვლა C; ანალოგიურად DFA-ის მდგომარეობის შესაბამისი ნაკრებისთვის ე). დასრულებულია DFA-ს მდგომარეობათა და გადასვლების ცხრილის აგების პროცესი.

DKA სახელმწიფო	NFA შტატების ნაკრები	ხტუნვადი პერსონაჟები
		ა	ბ	გ
ა	{1, 2, 9}	ბ	-	C
ბ	{3, 4, 6}	-	დ	ე
C	{10}	-	-	-
დ	{2, 5, 8, 9}	ბ	-	C
ე	{2, 7, 8, 9}	ბ	-	C

შედეგი:

მარჯვენა წრფივი გრამატიკის აგება სასრული ავტომატიდან

თითოეული სახელმწიფო ასოცირდება არატერმინალთან. თუ არის სახელმწიფო გარდამავალი Xსახელმწიფოში ი on ა, დაამატე წესი X → aY. საბოლოო ქვეყნებისთვის დაამატეთ წესები X→ ე. ε-გადასვლებისთვის - X → ი.

მაგალითი 1 (განმსაზღვრელი მდგომარეობის მანქანა)

• A → აბ | გ C
• B → ბ D | გე
• C → ე
• D → აბ | გ C
• E → აბ | გ C

მაგალითი 2 (არადეტერმინისტული მდგომარეობის მანქანა)

• 1 → 2 | 9
• 2 → ა 3
• 3 → 4 | 6
• 4 → ბ 5
• 5 → 8
• 6 → გ 7
• 7 → 8
• 8 → 2 | 9
• 9 → გ 10
• 10 → ε

DFA-ს მშენებლობა RV-ის მიერ

მოდით, რეგულარული გამოხატვა გვქონდეს რ. ამ რეგულარულ გამოხატულებაზე დაყრდნობით, აუცილებელია დეტერმინისტული სასრული ავტომატის აგება დისეთივე როგორც ლ(დ) = ლ(რ).

რეგულარული გამოხატვის მოდიფიკაცია

დავუმატოთ მას სიმბოლო, რაც ნიშნავს RV-ს დასასრულს - "#". შედეგად, ჩვენ ვიღებთ რეგულარულ გამოხატულებას ( რ)#.

ხის აშენება

წარმოვიდგინოთ რეგულარული გამოხატულება, როგორც ხე, რომლის ფოთლები ტერმინალური სიმბოლოებია, ხოლო შიდა კვანძები არის შეერთების ოპერაციები ".", კავშირი "∪" და გამეორება "*". ჩვენ ვანიჭებთ უნიკალურ რიცხვს ხის თითოეულ ფოთოლს (გარდა ε-ფოთლებისა) და ვუწოდებთ მას, ერთის მხრივ, როგორც პოზიცია ხეში და, მეორე მხრივ, როგორც სიმბოლოს პოზიცია, რომელიც შეესაბამება ფოთოლი.

ფუნქციების გაანგარიშება nullable, firstpos, lastpos

ახლა, T ხეზე ქვემოდან ზემოდან მარცხნიდან მარჯვნივ, ჩვენ ვიანგარიშებთ სამ ფუნქციას: ნულოვანი, პირველი, და ბოლო. ფუნქციები ნულოვანი, პირველიდა ბოლოგანსაზღვრულია ხის კვანძებში. ყველა ფუნქციის მნიშვნელობა გარდა ნულოვანი, არის პოზიციების ნაკრები. ფუნქცია პირველი(ნ) რეგექსის სინტაქსის ხის თითოეული კვანძისთვის n იძლევა პოზიციების ერთობლიობას, რომლებიც ემთხვევა პირველ სიმბოლოებს ქვესტრიქონებში, რომლებიც წარმოიქმნება ქვეგამოსახულებით, რომელიც მთავრდება ნ. ანალოგიურად, ბოლო(ნ) იძლევა პოზიციების ერთობლიობას, რომლებიც შეესაბამება ქვესტრიქონების ბოლო სიმბოლოებს, რომლებიც წარმოიქმნება ზედა გამოსახულებების მიერ ნ. კვანძებისთვის ნ, რომლის ქვეხეები (ანუ ხე, რომლის კვანძი ნარის ფესვი) შეუძლია ცარიელი სიტყვის გენერირება, ჩვენ განვსაზღვრავთ ნულოვანი(ნ) = მართალიადა სხვა კვანძებისთვის ყალბი. ცხრილი გამოსათვლელად ნულოვანი, პირველი, ბოლო:

კვანძი ნ	ნულოვანი(ნ)	პირველი(ნ)	ბოლო(ნ)
ε	მართალია	∅	∅
მე ≠ ε	ყალბი	{მე}	{მე}
u ∪ v	ნულოვანი(u) ან ნულოვანი(ვ)	პირველი(u) ∪ პირველი(ვ)	ბოლო(u) ∪ ბოლო(ვ)
თქვენ . ვ	ნულოვანი(u) და ნულოვანი(ვ)	თუ ნულოვანი(u) შემდეგ პირველი(u) ∪ პირველი(ვ) სხვა პირველი(u)	თუ ნულოვანი(ვ) შემდეგ ბოლო(u) ∪ ბოლო(ვ) სხვა ბოლო(ვ)
v*	მართალია	პირველი(ვ)	ბოლო(ვ)

შენობის მიმდევრები

ფუნქცია შემდგომიგამოითვლება მეშვეობით ნულოვანი, პირველიდა ბოლო. ფუნქცია შემდგომიგანსაზღვრულია მრავალ პოზიციაზე. მნიშვნელობა შემდგომიარის პოზიციების ნაკრები. Თუ მე- მაშინ პოზიცია შემდგომი(მე) ბევრი პოზიციაა ჯისეთი, რომ არის რაღაც სიმები... cd... შედის RW-ს მიერ აღწერილ ენაში, ისეთი რომ მეშეესაბამება ამ ჩანაწერს გ, ა ჯ- შესვლა დ. ფუნქცია შემდგომიასევე შეიძლება გამოითვალოს ხის ერთ გადაკვეთაზე შემდეგი ორი წესის მიხედვით

1. დაე იყოს ნ- შიდა კვანძი "." (შეერთება); ა, ბ- მისი შთამომავლები. შემდეგ თითოეული პოზიციისთვის მეშეიცავს ბოლო(ა შემდგომი(მე) რამოდენიმე პირველი(ბ).
2. დაე იყოს ნ- შიდა კვანძი "*" ოპერაციით (გამეორება), ა- მისი შთამომავალი. შემდეგ თითოეული პოზიციისთვის მეშეიცავს ბოლო(ა), დაამატეთ მნიშვნელობების სიმრავლეს შემდგომი(მე) რამოდენიმე პირველი(ა).

მაგალითი

გამოთვალეთ ფუნქციის მნიშვნელობა შემდგომირეგულარული გამოხატვისთვის ( ა(ბ|გ))*გ.

თანამდებობა	მნიშვნელობა შემდგომი
1: (ა (ბ|გ))*გ	{2, 3}
2: (ა(ბ |გ))*გ	{1, 4}
3: (ა(ბ|გ ))*გ	{1, 4}
4: (ა(ბ|გ))*გ	{5}

DFA-ს აგება

DFA არის მდგომარეობათა და მათ შორის გადასვლების ერთობლიობა. DFA სახელმწიფო არის პოზიციების ერთობლიობა. DFA-ს აგება მოიცავს მასში აუცილებელი მდგომარეობების თანდათანობით დამატებას და მათთვის გადასვლების აგებას. თავდაპირველად, არსებობს ერთი სახელმწიფო პირველი(ფესვი) (ფესვი- ხის ფესვი), რომელსაც არ აქვს გადასვლები. გადასვლა ხორციელდება სიმბოლოებით რეგულარული გამოხატვისგან. თითოეული სიმბოლო შეესაბამება პოზიციების ერთობლიობას ( გვ მე). ყველას გაერთიანება შემდგომი(x) არის მდგომარეობა, სადაც აუცილებელია წასვლა, სადაც x არის პოზიცია, რომელიც იმყოფება როგორც მდგომარეობის პოზიციებს შორის, ასევე სიმბოლოს პოზიციებს შორის RE-დან, რომელზედაც ხდება გადასვლა. თუ ასეთი მდგომარეობა არ არის, მაშინ ის უნდა დაემატოს. პროცესი უნდა განმეორდეს მანამ, სანამ არ აშენდება ყველა გადასვლები ყველა სახელმწიფოსთვის. ყველა მდგომარეობა, რომელიც შეიცავს RE-ს ბოლოს დამატებული # სიმბოლოს პოზიციას, გამოცხადებულია საბოლოო.

DFA მიღებული RV-დან ( ა(ბ|გ))*გ

მაგალითი

შექმენით DFA რეგულარული გამოსახულებით ( ა(ბ|გ))*გ.

DKA სახელმწიფო	სიმბოლო
	a (1)	b(2)	c(3, 4)
A(1, 4)	B(2, 3)	-	C(5)
B(2, 3)	-	A(1, 4)	A(1, 4)
C(5)	-	-	-

DFA-ს შექმნა სახელმწიფოების მინიმალური რაოდენობით

DFA მდგომარეობების მინიმალური რაოდენობით აგებულია ყველგან განსაზღვრული DFA-სთვის, ე.ი. ისეთივე როგორც . ნებისმიერი DFA-სთვის არსებობს ყველგან განსაზღვრული DFA მისი ექვივალენტი.

ყველგან განსაზღვრული DFA-ის მშენებლობა

შემოიღეთ ახალი მდგომარეობა და განსაზღვრეთ სახელმწიფოების ახალი ნაკრები .

მოდით განვსაზღვროთ ახალი გადასვლის ფუნქცია ასე:

დანაყოფის აგება (ფორმალურად)

მოდით ავაშენოთ საწყისი დანაყოფი პმდგომარეობების ნაკრები ორ ჯგუფად: საბოლოო მდგომარეობები ფდა სხვა S/F, ე.ი. პ = {ფ, Q\F}.

მიმართეთ თითოეულ ჯგუფს გ ∈ პშემდეგი პროცედურა. დამსხვრევა გქვეჯგუფებად ისე, რომ სახელმწიფოები სდა ტდან გდასრულდა იმავე ჯგუფში, თუ და მხოლოდ თუ თითოეული შეყვანის სიმბოლოსთვის აშტატები სდა ტაქვს გადასვლები აიმავე ჯგუფის ქვეყნებში პ.

შედეგად მიღებული ქვეჯგუფები ემატება ახალ დანაყოფს პახალი.

მიღება პ = პახალი და გაიმეორეთ დანაყოფის კონსტრუქცია სტაბილიზაციამდე, ანუ სანამ დანაყოფი არ შეწყვეტს შეცვლას.

დანაყოფის აგება (ალგორითმი)

დანაყოფის ასაგებად, არსებობს შემდეგი ალგორითმი. ჩვენ ვაშენებთ გარდამავალ ცხრილს ორიგინალური ავტომატისთვის, ვაშენებთ თავდაპირველ დანაყოფს.

თითოეულ ჯგუფს ვანიჭებთ იდენტიფიკატორს დანაყოფიდან (საწყისი დანაყოფისთვის, მაგალითად, 0 და 1).

თითოეულ მდგომარეობას (ცხრილის თითოეულ სტრიქონს) ენიჭება სტრიქონი ფორმის "a.bcd...xyz", სადაც არის იმ ჯგუფის იდენტიფიკატორი, რომელსაც სახელმწიფო ეკუთვნის [პირველი სვეტიდან (სადაც მივდივართ), მეორედან. სვეტი (სადაც მივდივართ პირველი სიმბოლოთი), …, ბოლო სვეტი (სადაც მივდივართ ბოლო სიმბოლოთი)].

ჩვენ ვაშენებთ ახალ ჯგუფებს სტრიქონების დამთხვევის მიხედვით, ანუ ისე, რომ იგივე მინიჭებული სტრიქონების მქონე მდგომარეობები ერთ ჯგუფში მოხვდება.

შემდეგ, ახალი გამეორება. მიღებულ ჯგუფებს ვანიჭებთ ახალ იდენტიფიკატორებს, მაგალითად (0, 1, ..., n). და ჩვენ ვიმეორებთ დანაყოფის მშენებლობას სტაბილიზაციამდე.

გაითვალისწინეთ, რომ როდესაც ჯგუფში რჩება მხოლოდ ერთი მდგომარეობა, დანაყოფის აგების შემდგომ ეტაპებზე, თქვენ აღარ შეგიძლიათ ამოწეროთ ამ მდგომარეობის იდენტიფიკატორების სტრიქონი, რადგან ეს სტრიქონი ნებისმიერ შემთხვევაში უნიკალური იქნება პირველი სიმბოლოს გამო. სიმებიანი. სხვა სიტყვებით რომ ვთქვათ, გაყოფისას ჯგუფს ერთი სახელმწიფოდან არაფერი დაემართება - ის გადადის ახალ გაყოფაზე, როგორც არის.

შემცირებული ავტომატის მშენებლობა

თითოეული მიღებული ჯგუფი ხდება ახალი DFA-ის მდგომარეობა. თუ ჯგუფი შეიცავს ორიგინალური ავტომატის საწყის (ფინალურ) მდგომარეობას, ეს ჯგუფი ხდება ახალი DFA-ის საწყისი (შესაბამისად საბოლოო) მდგომარეობა. გადასვლები აგებულია აშკარად: ჯგუფიდან მდგომარეობაზე გადასვლა ითვლება ჯგუფზე გადასვლად.

მანქანა მოვიყვანეთ. ჩვენ ჯერ ვხსნით არაწარმომქმნელს (სტერილურს, "მკვდარ"), მაშინმიუწვდომელი მდგომარეობები (სიმბოლოებისთვის მოცემულია განმარტებები, მაგრამ აშკარად ისინი გადადის ავტომატის მდგომარეობებზე).

ზოგადად რომ ვთქვათ, მკვდარი მდგომარეობების ამოღება აქცევს DFA-ს NFA-ად, რადგან DFA-ში ყველა გადასვლები უნდა იყოს განსაზღვრული. თუმცა, დრაკონის წიგნში ფორმალური განმარტებიდან ასეთი გადახრა მაინც მისაღებია.

მაგალითი

ააგეთ DFA მდგომარეობების მინიმალური რაოდენობით შემდეგი ფორმის DFA-სთვის:

• საწყისი გაყოფა: (C) ( საბოლოო მდგომარეობა), (A, B, D, E) ( ყველა სხვა სახელმწიფო).
• (C)( ცვლილებების გარეშე), (A, D, E), (B), ( ვინაიდან A, D, E-დან a, c-ზე გადავდივართ B და C-ზე, შესაბამისად).
• მეტი გაყოფა არ შეგვიძლია.

მოდით ჯგუფი (C) შეესაბამებოდეს C მდგომარეობას, ჯგუფი (A, D, E) A მდგომარეობას და ჯგუფი (B) B მდგომარეობას. შემდეგ მივიღებთ DFA მდგომარეობების მინიმალური რაოდენობით:

მაგალითი (დანაყოფის აგების ალგორითმი)

გადასვლის ცხრილი ყველგან განსაზღვრული (დამატებულია Z მდგომარეობა) DFA, რომელიც შეესაბამება RV (ab|ε)a*|abb|b*a. 2012 წლის საგამოცდო კითხვებიდან.

	ა	ბ	მე 0	მე 1
→A*	ბ	C	0.01	0.12
B*	დ	ე	0.00	1.01
C	ფ	C	1.01
დ*	დ	ზ	0.01	0.04
E*	დ	ზ	0.00	1.03
F*	ზ	ზ	0.11
ზ	ზ	ზ	1.11

გამეორებები:

• I 0: ABCDEF(0), CZ(1).
• I 1: AD(0), BE(1), C(2), F(3), Z(4).
• I 2: A, B, C, D, E, F, Z.

შედეგი: მანქანას უკვე ჰქონდა მდგომარეობის მინიმალური რაოდენობა :-)

DFA, რომელიც საშუალებას აძლევს ენის დასრულებას

DFA-ის აგების ალგორითმი, რომელიც იღებს ენის L (L̅) კომპლემენტს, შედგება ორი ეტაპისგან:

• სრული DFA-ს შექმნა
• მისგან სასურველი ავტომატის კონსტრუქცია

სინამდვილეში, სრული DFA არ არსებობს. სრული DKA-ს ქვეშ ზოგიერთიმასწავლებლებს ესმით ავტომატი, რომლის გარდამავალ ცხრილში არ არის ცარიელი უჯრედები. თუმცა, DFA განსაზღვრების მიხედვით - δ: Q × Σ → Q - არ შეიძლება იყოს ცარიელი უჯრედები ნებისმიერ შემთხვევაში. ავტომატი "ცარიელი უჯრედებით", თუმცა აკმაყოფილებს NFA-ს განმარტებას. გადაჭრის პროცესში იშვიათი არაა სწორედ ასეთი NFA-ს მიღება, რომელსაც აკლია მხოლოდ გადასვლები DFA-მდე.

მის შესავსებად საკმარისია ახალი მდგომარეობის დამატება X, და არარსებული გადასვლების "ნაცვლად" ამ ახალ მდგომარეობას ამატებენ გადასვლებს. არ დაგავიწყდეთ, დაამატოთ გადასვლები X in X. ადვილი მისახვედრია, რომ სადაც თავდაპირველმა ავტომატმა არ მიიღო გარკვეული ჯაჭვი გადასვლის არარსებობის გამო, ახალი ავტომატი გადავა მდგომარეობაში Xდა დაკიდე მასზე. ვინაიდან ახალი მდგომარეობა არ არის მიმღები (საბოლოო) მდგომარეობა, ახალი ავტომატი ასევე არ მიიღებს ამ ჯაჭვს.

ახლა სასურველი ავტომატის ასაგებად საჭიროა მხოლოდ მიმღები და არამიმღები სახელმწიფოების როლების შეცვლა. სხვა სიტყვებით რომ ვთქვათ, F" = Q \ F.

LL(k) ანალიზატორის აგება

გრამატიკული ტრანსფორმაცია

ყველა გრამატიკა არ არის LL(k)-გაანალიზებადი. კონტექსტის გარეშე გრამატიკა ეკუთვნის LL(1) კლასს, თუ მას არ აქვს FIRST-FIRST კონფლიქტები (მარცხენა რეკურსია არის ასეთი კონფლიქტის განსაკუთრებული შემთხვევა) და FIRST-FOLLOW.

ზოგჯერ შესაძლებელია არა-LL(1) გრამატიკების გარდაქმნა ისე, რომ ისინი გახდნენ LL(1). ზოგიერთი (უფრო ზუსტად, ის, რაც კურსში იყო გათვალისწინებული) ტრანსფორმაციები მოცემულია ქვემოთ.

მარცხენა რეკურსიის წაშლა

დავუშვათ, რომ გვაქვს ფორმის წესი (შემდგომში ამ განყოფილებაში დიდი ასოები - არატერმინალური სიმბოლოები, პატარა - ნებისმიერი პერსონაჟის ჯაჭვები):

• A→A ა| ა ბ| … | ა კ | მ | ნ | … | ზ

ის არ ექვემდებარება ცალსახა ანალიზს, ამიტომ უნდა გადაკეთდეს.

ადვილია იმის ჩვენება, რომ ეს წესი უდრის შემდეგი წესების წყვილს:

• A → მბ | ნბ | … | ზბ
• B → აბ | ბბ | … | კბ | ე

მარცხენა ფაქტორიზაცია

ამ პროცედურის არსი არის ბუნდოვანების აღმოფხვრა მარცხენა სიმბოლოს წესების არჩევისას. ამისათვის ნაპოვნია საერთო მარცხენა პრეფიქსი და რა შეიძლება მოჰყვეს მას, ამოღებულია ახალი წესით (პატარა ასოები - ნებისმიერი პერსონაჟის ჯაჭვები)

მაგალითი

• A → აგ | ადფ | ადგ | ბ

გადაკეთდა

• A → აბ | ბ
• B → გ | დვ | დგ

რაც თავის მხრივ ხდება

• A → აბ | ბ
• B → გ | დთან
• C → ვ | გ

გრამატიკის კონვერტაციის მაგალითი

გ= ((S, A, B), (a, b, c), P, S)

• S→SAbB | ა
• A→ab | აა | ე
• B → c | ე

მარცხენა რეკურსიის წაშლა S:

• S → aS 1
• S 1 → AbBS 1 | ე

მარცხენა ფაქტორიზაცია ა:

• A → aA 1 | ე
• A 1 → b | ა

საბოლოო გრამატიკა:

• S → aS 1
• S 1 → AbBS 1 | ე
• A → aA 1 | ე
• A 1 → b | ა
• B → c | ე

აშენება FIRST და FOLLOW

FIRST(α), სადაც α ∈ (N ∪ T)* არის ტერმინალების ნაკრები, საიდანაც α შეიძლება დაიწყოს. თუ α ⇒ ε, მაშინ ε ∈ FIRST(α). შესაბამისად, მნიშვნელობა FOLLOW( ა) არატერმინალისთვის ა- ბევრი ტერმინალი, რომელიც შეიძლება გამოჩნდეს მაშინვე არაღაც სენტიმენტალური ფორმით. Თუ აშეიძლება იყოს ყველაზე მარჯვენა სიმბოლო რომელიმე წინადადების ფორმაში, მაშინ საბოლოო $ ჟეტონი ასევე ეკუთვნის FOLLOW( ა)

პირველი გაანგარიშება

ტერმინალებისთვის

• ნებისმიერი ტერმინალისთვის x, x ∈ თ, ᲞᲘᲠᲕᲔᲚᲘ( x) = {x}

არატერმინალებისთვის

• Თუ Xარის არატერმინალი, შემდეგ ჩვენ ვაყენებთ FIRST( X) = {∅}
• თუ გრამატიკას აქვს წესი X→ ε, შემდეგ დაამატეთ ε FIRST( X)
• ყოველი არატერმინალისთვის Xდა თითოეული დასკვნის წესისთვის X → ი 1 …ი k დამატება FIRST-ში( X) ყველა სიმბოლოს პირველი კომპლექტი წესის მარჯვენა მხარეს პირველამდე, საიდანაც ε არ არის მიღებული, მისი ჩათვლით

ჯაჭვებისთვის

• სიმბოლოების სტრიქონისთვის X 1 …X k FIRST არის FIRST სიმბოლოების გაერთიანება, რომელიც შედის სტრიქონში პირველამდე, რომელსაც აქვს ε ∉ FIRST მის ჩათვლით.

მაგალითი

• S → aS 1
• S 1 → AbBS 1 | ე
• A → aA 1 | ე
• A 1 → b | ა
• B → c | ე

FIRST არატერმინალები დამოკიდებულების გადაწყვეტის თანმიმდევრობით:

• FIRST(S) = (a)
• FIRST(A) = (a, ε)
• FIRST(A 1) = (b, a)
• FIRST(B) = (c, ε)
• FIRST(S 1) = (a, b, ε)

პირველი დასკვნის წესებისთვის:

• FIRST(aS 1) = (a)
• FIRST(AbBS 1) = (a, b)
• FIRST(ε) = (ε)
• FIRST(aA 1) = (a)
• FIRST(a) = (a)
• FIRST(ბ) = (ბ)
• FIRST(c) = (c)

დაიცავით გაანგარიშება

FOLLOW ფუნქციის გამოთვლა სიმბოლო X-ისთვის:

• მოდით FOLLOW(X) = (∅)
• თუ X არის გრამატიკული აქსიომა, მაშინ დაამატეთ მარკერი $ FOLLOW-ს
• A ფორმის ყველა წესისთვის → αXβ დაამატეთ FIRST(β)\(ε) FOLLOW(X)-ს (X შეიძლება მოჰყვეს იმ სიმბოლოებს, რომლებიც იწყება β-ით)
• A → αX და A → αXβ, ε ∈ FIRST(β) ფორმის ყველა წესისთვის დაამატეთ FOLLOW(A) FOLLOW(X)-ს (ანუ, X შეიძლება მოჰყვეს ყველა სიმბოლოს, რომელიც შეიძლება მოჰყვეს A-ს, თუ დასკვნის წესი, X შეიძლება იყოს შორს მარჯვნივ)
• გაიმეორეთ წინა ორი აბზაცი მანამ, სანამ შესაძლებელია ნაკრებში სიმბოლოების დამატება

მაგალითი

• S → aS 1
• S 1 → AbBS 1 | ე
• A → aA 1 | ე
• A 1 → b | ა
• B → c | ე

შედეგი:

• FOLLOW(S) = ($)
• FOLLOW(S 1) = ($) (S 1 არის ყველაზე მარჯვენა სიმბოლო წესში S → aS 1)
• FOLLOW(A) = (b) (A წესში S 1 → AbBS 1 მოჰყვება b)
• FOLLOW(A 1) = (b) (A 1 არის ყველაზე მარჯვენა სიმბოლო A → aA 1 წესში, შესაბამისად დავამატებთ FOLLOW(A) FOLLOW(A 1)))
• FOLLOW(B) = (a, b, $) (დაამატე FIRST(S 1)\(ε) (გამოდის წესიდან S 1 → AbBS 1), FOLLOW(S 1) (რადგან არის S 1 → ε))

ცხრილის შედგენა

მაგიდა მარატერმინალურ-ტერმინალური წყვილისთვის (უჯრედში მ[ა, ა]) განსაზღვრავს წესს, რომლითაც შეყვანილი სიტყვა უნდა შემცირდეს. ცხრილი ივსება შემდეგნაირად: მოცემული გრამატიკის A → α დასკვნის თითოეული წესისთვის (სადაც α იგულისხმება, როგორც წესის მარჯვენა მხარეს არსებული ჯაჭვი), შესრულებულია შემდეგი მოქმედებები:

1. თითოეული ტერმინალისთვის ა∈ FIRST(α) დაამატეთ წესი ა → α რომ მ[ა, ა]
2. თუ ε ∈ FIRST(α), მაშინ თითოეულისთვის ბ∈ მიყევით( ა) დაამატეთ ა → α რომ მ[ა, ბ]
3. ε ∈ FIRST(α) და $ ∈ FOLLOW( ა), დაამატეთ ა → α რომ მ[ა, $]
4. ყველა ცარიელი უჯრედი არის შეცდომა შეყვანილ სიტყვაში

მაგალითი

შექმენით ცხრილი გრამატიკისთვის

• S → aS 1
• S 1 → AbBS 1 | ე
• A → aA 1 | ე
• A 1 → b | ა
• B → c | ე

შედეგი:

	ა	ბ	გ	$
ს	S → aS 1 (პირველი წესი, დასკვნა S → aS 1 , a ∈ FIRST(aS 1))	შეცდომა (მეოთხე წესი)	შეცდომა (მეოთხე წესი)	შეცდომა (მეოთხე წესი)
S1	S 1 → AbBS 1 (პირველი წესი, გამომავალი S 1 → AbBS 1 , a ∈ FIRST(AbBS 1))	S 1 → AbBS 1 (პირველი წესი, გამომავალი S 1 → AbBS 1 , b ∈ FIRST (AbBS 1))	შეცდომა (მეოთხე წესი)	S 1 → ε (მესამე წესი, დასკვნა S 1 → ε, ε ∈ FIRST(ε), $ ∈ FOLLOW(S 1))
ა	A → aA 1 (პირველი წესი, გამომავალი A → aA 1 , a ∈ FIRST(aA 1))	A→ε (მეორე წესი, გამომავალი A 1 → ε, b ∈ FOLLOW(A 1))	შეცდომა (მეოთხე წესი)	შეცდომა (მეოთხე წესი)
A 1	A 1 → ა (პირველი წესი, გამომავალი A 1 → a, a ∈ FIRST(a))	A 1 → ბ (პირველი წესი, გამომავალი A 1 → b, b ∈ FIRST(b))	შეცდომა (მეოთხე წესი)	შეცდომა (მეოთხე წესი)
ბ	B→ε	B→ε (მეორე წესი, დასკვნა B → ε, a ∈ FOLLOW(B))	B → გ (პირველი წესი, გამომავალი B → c, c ∈ FIRST(c))	B→ε (მესამე წესი, დასკვნა B → ε, $ ∈ FOLLOW(B))

სტრიქონების გარჩევა

სტრიქონის გარჩევის პროცესი საკმაოდ მარტივია. მისი არსი შემდეგია: ყოველ ნაბიჯზე იკითხება ზედა სიმბოლო ვ გშეყვანის ჯაჭვი.

• Თუ ვ- ტერმინალის სიმბოლო
  • Თუ ვემთხვევა თან, მერე ორივე განადგურებულია, არის ცვლა
  • Თუ ვარ ემთხვევა თან, მაშინ სიგნალი მიიღება გაანალიზების შეცდომის შესახებ
• Თუ ვ- არატერმინალური სიმბოლო, გნაცვლად უბრუნდება ხაზის დასაწყისში ვწესის მარჯვენა მხარე, რომელიც აღებულია ცხრილის უჯრიდან, ბრუნდება სტეკში მ[ვ, გ]

პროცესი მთავრდება, როდესაც სტრიქონიც და სტეკიც მიაღწევენ ბოლო მარკერს (#).

მაგალითი

მოდით გავაანალიზოთ სტრიქონი "aabbaabcb":

დასტის	ხაზი	მოქმედება
ს#	ა abbaabcb$	S → aS 1
ა S1#	ა abbaabcb$	ცვლა
S1#	ა bbaabcb$	S 1 → AbBS 1
ა bbs 1#	ა bbaabcb$	A → aA 1
ა A 1 bBS 1 #	ა bbaabcb$	ცვლა
A 1 bbs 1#	ბ baabcb$	A 1 → ბ
ბ bbs 1#	ბ baabcb$	ცვლა
ბ B.S. 1#	ბ aabcb$	ცვლა
ბ S1#	ა abcb$	B→ε
S1#	ა abcb$	S 1 → AbBS 1
ა bbs 1#	ა abcb$	A → aA 1
ა bbs 1#	ა abcb$	A → aA 1
ა A 1 bBS 1 #	ა abcb$	ცვლა
A 1 bbs 1#	ა bcb$	A 1 → ა
ა bbs 1#	ა bcb$	ცვლა
ბ B.S. 1#	ბ cb$	ცვლა
ბ S1#	გბ$	B → გ
გ S1#	გბ$	ცვლა
S1#	ბ$	S 1 → AbBS 1
ა bbs 1#	ბ$	A→ε
ბ B.S. 1#	ბ$	ცვლა
ბ S1#	$	B→ε
S1#	$	S 1 → ε
#	$	მზადაა

LR(k) ანალიზატორის აგება

k-ის გამოთვლა LR(k)-ში

არ არსებობს ალგორითმი, რომელიც საშუალებას მისცემს, ზოგად შემთხვევაში, გამოთვალოს k თვითნებური გრამატიკისთვის. როგორც წესი, ღირს LR(1) პარსერის აშენების მცდელობა. თუ მას აქვს მაქსიმუმ ერთი ოპერაცია თითო კომპლექტში (Shift, Reduce ან Accept), მაშინ გრამატიკა არის LR(0). თუმცა, თუ კონფლიქტი და შეჯახება მოხდა LR(1) პარსერის აგებისას, მაშინ ეს გრამატიკა არ არის LR(1) და ღირს LR(2) აშენების მცდელობა. თუ ის ვერ ააგებს, მაშინ LR(3) და ა.შ.

გრამატიკის დასრულება

დავამატოთ ახალი წესი S" → S და S" გავხადოთ გრამატიკის აქსიომად. ეს დამატებითი წესი საჭიროა იმის დასადგენად, თუ როდის წყდება ანალიზატორი და დაშვებულია შეყვანის ჯაჭვი. მიღება ხდება მაშინ და მხოლოდ იმ შემთხვევაში, თუ შესაძლებელია კონვოლუციის განხორციელება S → S წესის მიხედვით“.

დასაშვები LR(1)-სიტუაციების სიმრავლეების კანონიკური სისტემის აგება

დასაწყისში არის I 0 ნაკრები ანალიზატორის კონფიგურაციით S" → .S, $. შემდეგ, დახურვის ოპერაცია გამოიყენება ამ კონფიგურაციაზე, სანამ მისი გამოყენების შედეგად არ დაემატება ახალი კონფიგურაციები. შემდეგი. , ახალ ნაკრებებზე გადასვლები აგებულია წერტილის ერთი სიმბოლოთი მარჯვნივ გადატანით (ნახტომები ხდება სიმბოლოთი, რომელიც იყო წერტილის შემდეგ ნახტომამდე და მის წინ ნახტომის შემდეგ) და იმ კონფიგურაციებით, რომლებიც მიღებულია არსებულიდან. ამ გზით ემატება ამ კომპლექტებს.დახურვის ოპერაცია ასევე გამოიყენება მათზე და მთელი პროცესი მეორდება მანამ, სანამ ახალი ნაკრები აღარ გამოჩნდება.

მაგალითი

შექმენით დასაშვები LR(1) სიტუაციების სიმრავლეების კანონიკური სისტემა მითითებული გრამატიკისთვის:

• S" → S
• S → ABA
• A → Aa | ე
• B → cBc | დ

გადაწყვეტილება:

• ჩვენ ვაშენებთ დახურვას კონფიგურაციისთვის S" → .S, $:
  • S → .ABA,$
• მიღებული კონფიგურაციებისთვის (S → .ABA, $) ჩვენ ასევე ვაშენებთ დახურვას:
  • A → .Aa, c
  • A → .Aa, d
  • A → .,გ
  • A → ., დ
• მიღებული კონფიგურაციებისთვის (A → .Aa, c; A → .Aa, d) ჩვენ ასევე ვაშენებთ დახურვას:
  • A → .Aa, a
  • A → ., ა
• I 0 მდგომარეობაში აღარ არის კონფიგურაციის აშენება - დახურვა აშენებულია

• I 0-დან შეგიძლიათ გააკეთოთ გადასვლები S და A-ს გასწვრივ და მიიღოთ I 1 და I 2 კონფიგურაციების ნაკრები, რომელიც შედგება შემდეგი ელემენტებისაგან:
  • I 1 = (S" → S., $)
  • I 2 = (S → A.BA, $; A → A.a, c; A → A.a, d; A → A.a, a)
• I 1 არ საჭიროებს დახურვას
• მოდით ავაშენოთ დახურვა I 2:
  • B → .cBc, a
  • B → .cBc, $
  • B → .d, a
  • B → .d, $
• ყველა სხვა კომპლექტი აგებულია ანალოგიურად.

პარსერის ცხრილის აგება

LR(1) პარსერის აგების საბოლოო ნაბიჯი არის ცხრილების აგება მოქმედებადა წადი. მაგიდა მოქმედებააგებულია სტრიქონის სიმბოლოების შეყვანისთვის, ანუ ტერმინალებისთვის და ხაზის ბოლო მარკერისთვის $, ცხრილისთვის წადიაგებულია გრამატიკული სიმბოლოებისთვის, ანუ ტერმინალებისთვის და არატერმინალებისთვის.

Goto მაგიდის აგება

Goto ცხრილი გვიჩვენებს, რომელ მდგომარეობაზე უნდა გადავიდეს შემდეგი გრამატიკული სიმბოლოს შეხვედრისას. ამიტომ, თუ სიმრავლეთა კანონიკურ სისტემაში ხდება გადასვლა მე მე in მე ჯსიმბოლოთ A, შემდეგ Goto-ში( მე მე, ა) ვდებთ სახელმწიფოს მე ჯ. ცხრილის შევსების შემდეგ, ჩვენ ვივარაუდებთ, რომ ყველა ცარიელ უჯრედში Goto( მე მე, ა) = შეცდომა

მოქმედებების ცხრილის აგება

• თუ ტერმინალზე a არის გადასვლა I მდგომარეობიდან I j მდგომარეობაზე, მაშინ მოქმედება(I i, a) = Shift(I j)
• თუ A ≠ S" და არის კონფიგურაცია A → α., a, მაშინ მოქმედება(I i, a) = შემცირება (A → α)
• I i მდგომარეობისთვის, რომელსაც აქვს კონფიგურაცია S" → S., $, მოქმედება(I i, $) = მიღება
• ყველა ცარიელი უჯრედისთვის მოქმედება(I i, a) = შეცდომა

მაგალითი

შექმენით Action და Goto ცხრილები გრამატიკისთვის

• S" → S
• S → ABA
• A → Aa | ე
• B → cBc | დ

გადაწყვეტილება:

	მოქმედება				წადი
	ა	გ	დ	$	ს	S"	ა	ბ	ა	გ	დ
მე 0	შემცირება (A → ε)	შემცირება (A → ε)	შემცირება (A → ε)		მე 1		მე 2
მე 1				მიღება
მე 2	Shift (I 6)	Shift (I 4)	Shift (I 5)					მე 3	მე 6	მე 4	მე 5
მე 3	შემცირება (A → ε)			შემცირება (A → ε)			მე 13
მე 4		Shift (I 8)	Shift (I 9)					მე 7		მე 8	მე 9
მე 5	შემცირება (B → d)			შემცირება (B → d)
მე 6	შემცირება (A → Aa)	შემცირება (A → Aa)	შემცირება (A → Aa)
მე 7		Shift (I 10)								მე 10
მე 8		Shift (I 8)	Shift (I 9)					მე 11		მე 8	მე 9
მე 9		შემცირება (B → d)
მე 10	შემცირება (B → cBc)			შემცირება (B → cBc)
მე 11		Shift (I 12)								მე 12
მე 12		შემცირება (B → cBc)
მე 13	Shift (I 14)			შემცირება (S → ABA)					მე 14
მე 14	შემცირება (A → Aa)			შემცირება (A → Aa)

ჯაჭვის გარჩევა

ყოველ ნაბიჯზე იკითხება მთავარი სიმბოლო ვანალიზატორის დასტადან და აიღეთ ბოლო სიმბოლო გშეყვანის ჯაჭვი.

თუ გადაკვეთაზე მოქმედებების ცხრილში ვდა გმდებარეობს:

• Shift ( ვიცი), შემდეგ დადეთ დასტაზე თანდა მერე ვიცი. სადაც გამოღებულია სიმიდან.
• შემცირება ( ა → u), შემდეგ ყველა ტერმინალური და არატერმინალური სიმბოლო, რომლებიც ქმნიან ჯაჭვს, გასუფთავდება სტეკის ზემოდან. u, რის შემდეგაც სახელმწიფო უყურებს მე მზევით დარჩენილი. გადაკვეთაზე გადასვლის ცხრილის მიხედვით მე მდა აიპოვნეთ შემდეგი მდგომარეობა მე ს. შემდეგ A უბიძგებს დასტაზე და შემდეგ მე ს. ხაზი უცვლელი რჩება.
• მიღება, შემდეგ გაანალიზება დასრულებულია
• სიცარიელე შეცდომაა

მაგალითი

მოდით ავაშენოთ aaaccdcc სტრიქონის ანალიზი:

დასტის	ხაზი	მოქმედება
მე 0	ა aaccdcc$	შემცირება (A → ε), მივიღე I 2
მე 0 ა მე 2	ა aaccdcc$	Shift (I 6)
მე 0 A მე 2 ა მე 6	ა accdcc$	შემცირება (A → Aa), მივიღე I 2
მე 0 ა მე 2	ა accdcc$	Shift (I 6)
მე 0 A მე 2 ა მე 6	ა ccdcc$	შემცირება (A → Aa), მივიღე I 2
მე 0 ა მე 2	ა ccdcc$	Shift (I 6)
მე 0 A მე 2 ა მე 6	გ cdcc$	შემცირება (A → Aa), მივიღე I 2
მე 0 ა მე 2	გ cdcc$	Shift (I 4)
I 0 A I 2 s მე 4	გ dcc$	Shift (I 8)
I 0 A I 2 c I 4 c მე 8	დ cc$	Shift (I 9)
I 0 A I 2 c I 4 c I 8 d მე 9	გ c$	შემცირება (B → d), მივიღე I 11
I 0 A I 2 c I 4 c I 8 B მე 11	გ c$	Shift (I 12)
I 0 A I 2 c I 4 c I 8 B I 11 c მე 12	გ$	შემცირება (B → cBc), მივიღე I 7
I 0 A I 2 c I 4 B მე 7	გ$	Shift (I 10)
I 0 A I 2 c I 4 B I 7 c მე 10	$	შემცირება (B → cBc), მივიღე I 3
I 0 A I 2 B მე 3	$	შემცირება (A → ε), მივიღე I 13
I 0 A I 2 B I 3 A მე 13	$	შემცირება (S → ABA), მივიღე I 1
მე 0 ს მე 1	$	მიღება

არითმეტიკული გამონათქვამების თარგმნა (Seti-Ullman ალგორითმი)

Შენიშვნა.კოდი გენერირებულია ძაღლის სტილის Motorola-ს მსგავსი, ე.ი.

Op Arg1, Arg2

დგას

Arg2 = Arg1 Op Arg2

ხის აშენება

ხე აგებულია, როგორც ყოველთვის, არითმეტიკული გამოსახულებისთვის: ძირში, ოპერაცია ყველაზე დაბალი პრიორიტეტით, რასაც მოჰყვება მოქმედებები ოდნავ უფრო მაღალი პრიორიტეტით და ა.შ. ფრჩხილებს აქვს უმაღლესი უპირატესობა. თუ არსებობს რამდენიმე ოპერაცია ერთი და იგივე პრიორიტეტით - a op b op c, მაშინ ხე აგებულია როგორც გამოსახულებისთვის (a op b) op c.

მაგალითი

ააგეთ ხე გამოსახულებისთვის a + b / (d + a − b × c / d − e) + c × d

გადაწყვეტილება:ჩვენ ვწერთ გამონათქვამს ფორმაში

((ა) + ((ბ) / ((((დ) + (ა)) − ((ბ) × (გ)) / (დ)) − (ე)))) + ((გ) × ( დ))

შემდეგ თითოეული ქვეხის ძირში იქნება ოპერაცია და ფრჩხილებში მარცხნივ და მარჯვნივ გამოსახულებები იქნება მისი ქვეხეები. მაგალითად, ქვეგამოსახულებისთვის ((b) × (c)) / (d), ოპერაცია „/“ იქნება შესაბამისი ქვეხის ძირში, ხოლო ქვეგამოხატვა ((b) × (c)) და (d). ) იქნება მისი ქვეხეები.

ხის განლაგება (რეგისტრების რაოდენობის გაანგარიშება)

• თუ წვერო არის მარცხენა ფოთოლი (ანუ ცვლადი), მაშინ მას ნულით ვნიშნავთ.
• თუ წვერო მარჯვენა ფოთოლია, მაშინ მას ერთით ვნიშნავთ
• თუ მის ორივე ქვეხეს რაიმე წვეროსთვის მოვნიშნავთ, მაშინ მას შემდეგნაირად აღვნიშნავთ:
  • თუ მარცხენა და მარჯვენა ქვეხეები სხვადასხვა ნომრით არის მონიშნული, აირჩიეთ მათგან ყველაზე დიდი
  • თუ მარცხენა და მარჯვენა ქვეხეებს ერთი და იგივე რიცხვები აქვთ, მაშინ ამ ქვეხეს ენიჭება რიცხვი, რომელიც ერთით მეტია ვიდრე ის, რომელიც ასახელებს ქვეხეებს.

ფოთლის ნიშნები	ხის განლაგება იდენტური ქვეხეებით	მარცხენა ქვეხეს აქვს დიდი რიცხვი	მარჯვენა ქვეხე იწერება დიდი რაოდენობით

მარჯვენა - იგივეროგორც წინაპარი.

თუ იარლიყი დატოვაშთამომავალი მეტიეტიკეტები უფლება, მაშინ უფლებაბავშვს ენიჭება რეესტრი კიდევ ერთივიდრე წინაპარი და დატოვა - იგივეროგორც წინაპარი.

კოდი იქმნება ხის ქვემოდან ზემოდან გადაკვეთით შემდეგნაირად:

1. არ არის გენერირებული კოდი წვეროსთვის ლეიბლით 0

2. თუ ზედა არის X ფურცელი 1 ეტიკეტით და დაარეგისტრირეთ R მე, შემდეგ კოდი

MOVE X, რი

3. თუ ზედა არის შიდა რეგისტრით R მედა მისი მარცხენა შვილი არის ფურცელი X ეტიკეტით 0, შემდეგ ის შეესაბამება კოდს

<Код правого поддерева>OpX, Ri

4. თუ წვეროს ქვეხეები რეგისტრით R მე- არ ტოვებს და მარჯვენა წვერის ეტიკეტი მეტია ან ტოლია მარცხენას ეტიკეტზე (რომელსაც აქვს რეგისტრი Rj, j = i + 1), მაშინ კოდი შეესაბამება წვეროს

<Код უფლებაქვეხე><Код დატოვაქვეხეები > Op Rj, Ri

5. თუ წვეროს ქვეხეები რეგისტრით R მე- არ ტოვებს და მარჯვენა წვერის ეტიკეტი (რისთვისაც რეგისტრი Rj, j = i + 1) ნაკლებია მარცხენას ეტიკეტზე, მაშინ კოდი შეესაბამება წვეროს.

რეგისტრის განაწილება ნაჩვენებია გრაფიკზე მარჯვნივ. გენერირებული კოდი:

MOVE d, R0 ;R0 = d MOVE c, R1 ;R1 = c MUL b, R1 ;R1 = (b × c) DIV R1, R0 ;R0 = (b × c) / d MOVE a, R1 ;R1 = a ADD d, R1 ;R1 = a + d SUB R1, R0 ;R0 = (a + d) − ((b × c) / d) MOVE e, R1 ;R1 = e SUB R0, R1 ;R1 = ((a + დ) − ((b × გ) / დ)) − e MOVE R1, R0; R0 = ((a + d) − ((b × c) / დ)) − e DIV b, R0 ;R0 = b / ((a + დ) − ((ბ × გ) / დ)) − ე) ADD a, R0 ;R0 = a + (b / (((a + d) − ((b × c) / d )) − e)) MOVE d, R1 ;R1 = d MUL c, R1 ;R1 = c × d ADD R0, R1 ;R1 = (a + (b / ((a + d) − ((b × c) ) / დ)) − e))) + (c × d) MOVE R1, R0;R0 = (a + (b / (((a + d) − ((b × c) / d)) − e) )) + (c × d)

ლოგიკური გამონათქვამების თარგმნა

ეს განყოფილება გვიჩვენებს, თუ როგორ უნდა გენერირება კოდი ლოგიკური გამონათქვამების ზარმაცი შეფასებისთვის. ალგორითმის შედეგად მიიღება კოდის ნაწილი, რომელიც TST, BNE, BEQ ოპერაციების გამოყენებით ითვლის ლოგიკურ გამოხატულებას ერთ-ერთ ეტიკეტზე: TRUELAB ან FALSELAB.

ხის აშენება

ლოგიკური გამოხატვის ხე ასახავს თანმიმდევრობას, რომლითაც იგი ფასდება ოპერაციების პრიორიტეტის მიხედვით, ანუ ხის კვანძის მნიშვნელობის შესაფასებლად (ეს არის ორი ოპერანდის მოქმედება, რომლებიც კვანძის ქვეხეებია), ჩვენ უნდა ჯერ გამოთვალეთ მისი ქვეხეების მნიშვნელობები.

ოპერაციის პრიორიტეტი: NOT ოპერატორს აქვს უმაღლესი უპირატესობა, რასაც მოჰყვება AND და შემდეგ OR. თუ გამონათქვამში გამოყენებულია სხვა ლოგიკური ოპერაციები, მაშინ ისინი უნდა იყოს გამოხატული ამ სამის მეშვეობით გარკვეული გზით (ჩვეულებრივ, სხვა ოპერაციები არ არსებობს და გამოხატვის კონვერტაცია არ არის საჭირო). იგივე პრიორიტეტის ოპერაციების ასოციაციურობა არის მარცხნიდან მარჯვნივ, ანუ A და B და C განიხილება როგორც (A და B) და C.

მაგალითი

ააგეთ ხე ლოგიკური გამოხატვისთვის არა A ან B და C და (B ან არა C).

გადაწყვეტილება:იხილეთ დიაგრამა მარჯვნივ.

ხის თითოეული წვეროსთვის გამოითვლება 4 ატრიბუტი:

• კვანძის ნომერი
• იარლიყი, რომელზედაც გადახვალთ, თუ კვანძში გამოთქმა მცდარია (false label, fl)
• ლეიბლი, რომელზეც უნდა გადახვიდეთ, თუ კვანძში გამოთქმა მართალია (true label, tl)
• იარლიყი-ნიშანი (ნიშანი) (დამატებითი ინფორმაციისთვის იხილეთ ქვემოთ)

წვეროები დანომრილია შემთხვევითი თანმიმდევრობით, ერთადერთი პირობაა კვანძების რიცხვების უნიკალურობა.

ხეების განლაგება კეთდება შემდეგნაირად:

• fl განსაზღვრავს იმ წვერის რაოდენობას, რომელზეც ხდება გადასვლა ან falselab თუ ეს წვერო მცდარია
• tl მიუთითებს იმ წვერის რაოდენობაზე, რომელზეც ხდება გადასვლა ან truelab-ს თუ ეს წვერო მართალია

ნიშანი მიუთითებს, თუ რა შემთხვევაში შეიძლება შეწყდეს მიმდინარე ქვეხის შეფასება.

ხის ფესვისთვის fl=falselab, tl=truelab, sign=false.

ამრიგად:

მაგალითი

მონიშნეთ ლოგიკური გამოხატვისთვის აგებული ხე არა A ან B და C და (B ან არა C).

კოდის გენერირება

გენერირებულ კოდში გამოყენებული აპარატის ბრძანებები:

• TST - არგუმენტის შემოწმება სიმართლისთვის და დროშის დაყენება, თუ არგუმენტი მცდარია
• BNE - გადადით ეტიკეტზე, თუ დროშა არ არის დაყენებული, ანუ მდგომარეობა შემოწმებულია TST-ით მართალია
• BEQ - გადადით ეტიკეტზე, თუ დროშა დაყენებულია, ანუ მდგომარეობა შემოწმებულია TST-ით ყალბი

კოდი აგებულია შემდეგნაირად:

• ხე იკვეთება ძირიდან, AND და OR-ისთვის ჯერ მარცხენა ქვეხე იკვეთება, შემდეგ მარჯვნივ.
• ყოველი გავლილი წვეროსთვის იბეჭდება მისი ნომერი (ეტიკეტი).
• ფურცლისთვის A (ნომერი, tl, fl, ნიშანი) იბეჭდება TST A
  • თუ ნიშანი == true, BNE tl იბეჭდება
  • თუ ნიშანი == false, BEQ fl იბეჭდება

მაგალითი

ზემოაღნიშნული გამონათქვამისთვის, შემდეგი კოდი გენერირებული იქნება:

1:2:4: TST A BEQ TRUELAB 3:5:7: TST B BEQ FALSELAB 8: TST C BEQ FALSELAB 6:9: TST B BNE TRUELAB 10:11: TST C BNE FALSELAB TRUELAB: FALSELAB:

ნიმუშის შესატყვისი მეთოდი

მეთოდის იდეა მდგომარეობს იმაში, რომ პროგრამის ერთი და იგივე განყოფილებისთვის კოდი შეიძლება შეიქმნას სხვადასხვა გზით და, შედეგად, ოპტიმიზაცია მიიღწევა ამა თუ იმ პარამეტრისთვის.

პრობლემის ფორმულირება

არსებობს მრავალი ნიმუში, რომელთაგან თითოეული განისაზღვრება შუალედური წარმოდგენის ნაწილით, რომლისთვისაც იგი გამოიყენება, წონა და გენერირებული კოდი. არსებობს შუალედური წარმომადგენლობის ხე, რომელიც არის პროგრამის ფრაგმენტი, რომლისთვისაც საჭიროა კოდის გენერირება. მიზანია შუალედური წარმომადგენლობითი ხის ნიმუშებით ისეთი საფარის აგება, რომ ნიმუშების საერთო წონა იყოს მინიმალური.

შაბლონები არის შეკრების ინსტრუქციები და მათ შესაბამისი გარჩევის ხეები. თითოეული ნიმუშისთვის ცნობილია მისი შესრულების დრო (ციკლებში). მათი დახმარებით ჩვენ გამოვქმნით ოპტიმალურ (შესრულების დროის თვალსაზრისით) კოდს.

ნიმუშების მაგალითები

შუალედური წარმომადგენლობის აგება

პირველ რიგში, ჩვენ ვაშენებთ გაანალიზების ხეს მთელი გამოხატვისთვის.

დაფარვის აგება

ახლა ყოველი წვეროსთვის (გავდივართ მათ თანმიმდევრობით ფოთლებიდან ფესვებამდე), გამოვქმნით მისი ქვეხის ოპტიმალურ კოდს. ამისათვის ჩვენ უბრალოდ გადავხედავთ ყველა ნიმუშს, რომელიც გამოიყენება მოცემულ წვეროზე. შესრულების დრო კონკრეტული ნიმუშის გამოყენებისას იქნება დროის ჯამი, რომელიც სჭირდება მისი არგუმენტების შეფასებას (და ჩვენ უკვე ვიცით მათი გამოთვლის ოპტიმალური კოდი ხეების გადაკვეთის რიგის წყალობით) და თავად ნიმუშის შესრულების დრო. ყველა მიღებული ვარიანტიდან ვირჩევთ საუკეთესოს - ეს იქნება ოპტიმალური კოდი ამ წვეროს ქვეხისთვის. ხის ფესვზე ვიღებთ ოპტიმალურ კოდს მთელი გამოხატვისთვის.

კოდის გენერირება

არ არის აუცილებელი ყველა წვეროსთვის კოდის ჩაწერა - საკმარისია ჩაწეროთ მინიმალური საჭირო დრო და ნიმუში, რომელიც უნდა გამოიყენოთ. აქედან ყველაფერი დანარჩენი ადვილად აღდგება.

ჩვენ გვაქვს უსასრულო რაოდენობის რეგისტრები ამ პრობლემებში, ასე რომ ყოველ ჯერზე შეგიძლიათ გამოიყენოთ ახალი.

RV-ის მშენებლობა DFA-ს მიხედვით

NFA-ს აგება მარჯვენა-წრფივი გრამატიკის მიხედვით

გრამატიკის ჩამოსხმა

თვითნებური COP-გრამატიკის შემცირებულ ფორმაში გადასაყვანად, თქვენ უნდა შეასრულოთ შემდეგი ნაბიჯები:

• ამოიღეთ ყველა უნაყოფო სიმბოლო;
• წაშალეთ ყველა მიუწვდომელი სიმბოლო;

უსარგებლო სიმბოლოების ამოღება

შესასვლელი: COP-გრამატიკა G = (T, N, P, S).

გამომავალი: COP-გრამატიკა G' = (T, N', P', S), რომელიც არ შეიცავს უნაყოფო სიმბოლოებს, რისთვისაც L(G) = L(G').

მეთოდი:

რეკურსიულად შექმენით კომპლექტები N 0 , N 1 , ...

1. N 0 = ∅, i = 1.
2. N i = (A | (A → α) ∈ P და α ∈ (N i - 1 ∪ T)*) ∪ N i-1 .
3. თუ N i ≠ N i - 1, მაშინ i = i + 1 და გადადით მე-2 საფეხურზე, წინააღმდეგ შემთხვევაში N’ = N i; P' შედგება P სიმრავლის წესებისგან, რომელიც შეიცავს მხოლოდ N' ∪ T სიმბოლოებს; G' = (T, N', P', S).

განმარტება:სიმბოლო x ∈ (T ∪ N) გრამატიკაში მიუწვდომელია G = (T, N, P, S), თუ ის არ ჩანს ამ გრამატიკის რომელიმე წინადადებაში.

მაგალითი

ამოიღეთ უსარგებლო სიმბოლოები გრამატიკიდან G((A, B, C, D, E, F, S), (a, b, c, d, e, f, g), P, S)

• S → AcDe | CaDbCe | საკა | aCb | dFg
• A → SeAd | cSA
• B → CaBd | aDBc | BSC | ბფგ
• C→Ebd | სებ | aAc | cfF
• D→fCE | ac | dEdAS | ე
• E→ESacD | aec | eFF

გადაწყვეტილება

• N 0 = ∅
• N 1 = (B (B → bfg) , D (D → ac) , E (E → aec) )
• N 2 = (B, D, E, C (C → Ebd) )
• N 3 = (B, D, E, C, S (S → aCb) )
• N 4 \u003d (B, D, E, C, S) \u003d N 3

G"((B, C, D, E, S), (a, b, c, d, e, f, g), P", S)

• S → CaDbCe | საკა | aCb
• B → CaBd | aDBc | BSC | ბფგ
• C→Ebd | სებ
• D→fCE | ac | ე
• E→ESacD | აეკ

მიუწვდომელი სიმბოლოების წაშლა

შესასვლელი: COP გრამატიკა G = (T, N, P, S)

გამომავალი: COP-გრამატიკა G' = (T', N', P', S), რომელიც არ შეიცავს მიუწვდომელ სიმბოლოებს, რისთვისაც L(G) = L(G').

მეთოდი:

1. V 0 = (S); მე = 1.
2. V i = (x | x ∈ (T ∪ N), (A → αxβ) ∈ P და A ∈ V i - 1 ) ∪ V i-1.
3. თუ V i ≠ V i - 1 , მაშინ i = i + 1 და გადადით მე-2 საფეხურზე, წინააღმდეგ შემთხვევაში N’ = V i ∩ N; T' = V i ∩ T; P' შედგება P სიმრავლის წესებისგან, რომელიც შეიცავს მხოლოდ V i-ს სიმბოლოებს; G' = (T', N', P', S).

განმარტება: COP-გრამატიკა G მცირდება, თუ ის არ შეიცავს მიუწვდომელ და სტერილურ სიმბოლოებს.

მაგალითი

წაშალეთ მიუწვდომელი სიმბოლოები გრამატიკიდან G"((B, C, D, E, S), (a, b, c, d, e, f, g), P", S)

• S → CaDbCe | საკა | aCb
• B → CaBd | aDBc | BSC | ბფგ
• C→Ebd | სებ
• D→fCE | ac | ე
• E→ESacD | აეკ

გადაწყვეტილება

• V 0 = (S)
• V 1 = (S, C (S → CaDbCe) , D (S → CaDbCe) , a (S → CaDbCe) , b (S → CaDbCe) , e (S → CaDbCe) )
• V 2 = (S, C, D, a, b, e, E (C → Ebd) , d (C → Ebd) , f (D → fCE) )
• V 3 = (S, C, D, E, a, b, d, e, f, c (E → ESacD) )
• V 4 \u003d (S, C, D, E, a, b, d, e, f, c) \u003d V 3

G""((C, D, E, S), (a, b, c, d, e, f), P"", S)

• S → CaDbCe | საკა | aCb
• C→Ebd | სებ
• D→fCE | ac | ე
• E→ESacD | აეკ

ჩანაწერში r სიმბოლოების ანბანის სიმბოლოებისა და ოპერაციების ნიშნების და ფრჩხილების საერთო რაოდენობის მიხედვით.

საფუძველი. ავტომატები 1: სიგრძის გამოსახატავებისთვის და ნაჩვენებია შემდეგ ფიგურაში.

ბრინჯი. 5.1.

გაითვალისწინეთ, რომ ამ სამი ავტომატიდან თითოეულს აქვს საბოლოო მდგომარეობების ნაკრებიშედგება ერთი სახელმწიფოსგან.

ინდუქციური ნაბიჯი. ახლა დავუშვათ, რომ თითოეულისთვის რეგულარული გამოხატულებასიგრძე<= k построен соответствующий НКА, причем у него единственное заключительное состояние. Рассмотрим произвольное რეგულარული გამოხატულება r სიგრძის k+1 . ბოლო ოპერაციიდან გამომდინარე, მას შეიძლება ჰქონდეს სამი ფორმადან ერთი: (r 1 + r 2), (r 1 r 2) ან (r 1) * . მოდით და იყოს NFA-ები, რომლებიც აღიარებენ L r1 და L r2 ენებს, შესაბამისად. ზოგადის დაკარგვის გარეშე, ჩვენ ვივარაუდებთ, რომ მათ აქვთ განსხვავებული მდგომარეობა: .

შემდეგ NFA, რომლის დიაგრამა ნაჩვენებია ნახ. 5.2 , ცნობს ენას .

ბრინჯი. 5.2.

ამ მანქანას აქვს სახელმწიფოთა ნაკრები, სადაც q 0 არის ახალი საწყისი მდგომარეობა, q f არის ახალი (უნიკალური!) საბოლოო მდგომარეობა და პროგრამა მოიცავს ავტომატურ პროგრამებს M 1 და M 2 და ოთხ ახალ გადასვლის ბრძანებას: . ცხადია, NFA M-ის მიერ აღიარებული ენა მოიცავს ყველა სიტყვას L-დან (M 1) და L-დან (M 2). მეორეს მხრივ, თითოეული სიტყვა იღებს q 0-დან q f-მდე და პირველი ნაბიჯის შემდეგ მისი გადამტანი გზა გადის q 0 1 ან q 0 2 . ვინაიდან M 1 და M 2 მდგომარეობები არ იკვეთება, მაშინ პირველ შემთხვევაში ეს ბილიკი q f-მდე შეიძლება მოხვდეს მხოლოდ -q f 1-დან გადასვლის გზით და შემდეგ . ანალოგიურად, მეორე შემთხვევაში.

გამოხატვისთვის, NFA-ს დიაგრამა, რომელიც აღიარებს ენას L r, ნაჩვენებია შემდეგ ფიგურაში.

ბრინჯი. 5.3.

ამ მანქანას აქვს სახელმწიფოთა ნაკრები , საწყისი მდგომარეობა q 0 = q 0 1 , საბოლოო მდგომარეობა q f =q f 2 , ხოლო პროგრამაში შედის ავტომატური პროგრამები M 1 და M 2 და ერთი ახალი ბრძანება - გადასვლა საბოლოო მდგომარეობიდან M 1 საწყის მდგომარეობაში M 2 , ე.ი. . აქ ასევე აშკარაა, რომ ნებისმიერი გზა q 0 = q 0 1-დან q f = q f 2-მდე გადის -გადასასვლელად q f 1-დან q 0 2-მდე. მაშასადამე, M-ის მიერ დაშვებული ნებისმიერი სიტყვა არის L M1-ის რომელიმე სიტყვის შეერთება L M2-დან რომელიმე სიტყვასთან) და ასეთი სიტყვების ნებისმიერი შეერთება დასაშვებია. ამიტომ, NFA M ცნობს ენას.

მოდით r = r 1 * . NFA-ს დიაგრამა, რომელიც ცნობს ენას L r =L r1* = L M1 * ნაჩვენებია ნახ. 5.3.

ბრინჯი. 5.3.

ამ მანქანას აქვს სახელმწიფოთა ნაკრები, სადაც q 0 არის ახალი საწყისი მდგომარეობა, q f არის ახალი (უნიკალური!) საბოლოო მდგომარეობა და პროგრამა მოიცავს ავტომატურ პროგრამას M 1 და ოთხ ახალ გადასვლის ბრძანებას: . ცხადია,. არა ცარიელი სიტყვისთვის w, გამეორების განმარტებით ზოგიერთი k >= 1-ისთვის სიტყვა w შეიძლება დაიყოს k ქვესიტყვებად: w=w 1 w 2 ... w k და ეს არის. თითოეული i= 1,... ,k სიტყვა w i ასახავს q 0 1 q f 1-ს. შემდეგ სიტყვისთვის w დიაგრამაზე M არის ბილიკი

აქედან გამომდინარე,. პირიქით, თუ რომელიმე სიტყვა თარგმნის q 0-ს q f-ად, მაშინ ის არსებობს ან მას ატარებს გზა q 0 1 -ტრანზიციით, საბოლოოდ q f 1-დან -გადასვლით მთავრდება q f . ამიტომ, ასეთი სიტყვა.

4.2 და 5.1 თეორემებიდან ჩვენ პირდაპირ ვიღებთ

დასკვნა 5.1. Ყველასთვის რეგულარული გამოხატულებაშეიძლება ეფექტურად ავაშენოთ დეტერმინისტული სასრული ავტომატი, რომელიც ამოიცნობს ამ გამონათქვამში წარმოდგენილ ენას.

ეს განცხადება ერთ-ერთი მაგალითია სინთეზის თეორემები: დავალების აღწერილობის მიხედვით (ენა, როგორც რეგულარული გამოხატულება) პროგრამა (DFA), რომელიც ახორციელებს მას, ეფექტურად არის აგებული. პირიქითაც მართალია - ანალიზის თეორემა.

თეორემა 5.2. თითოეული დეტერმინისტული (ან არადეტერმინისტული) სასრული ავტომატისთვის შეიძლება აშენდეს რეგულარული გამოხატულება, რომელიც წარმოადგენს ამ ავტომატის მიერ აღიარებულ ენას.

ამ თეორემის დადასტურება საკმაოდ ტექნიკურია და სცილდება ჩვენი კურსის ფარგლებს.

ამრიგად, შეგვიძლია დავასკვნათ, რომ სასრული ავტომატის ენების კლასი ემთხვევა კლასს ჩვეულებრივი ენები. შემდეგში ჩვენ უბრალოდ დავარქმევთ მას ავტომატის ენების კლასი.

ავტომატი M r, რომელიც აგებულია თეორემა 5.1-ის დადასტურებაში

ძირითადი განმარტებები ანბანის Σ რეგულარული გამონათქვამები და მათი აღმნიშვნელი რეგულარული სიმრავლეები განიმარტება რეკურსიულად შემდეგნაირად: 1) რეგულარული გამოსახულება, რომელიც აღნიშნავს რეგულარულ სიმრავლეს; 2) e არის რეგულარული გამოხატულება, რომელიც აღნიშნავს რეგულარულ სიმრავლეს (e); 3) თუ Σ, მაშინ a არის რეგულარული გამოხატულება, რომელიც აღნიშნავს რეგულარულ სიმრავლეს (a); 4) თუ p და q არის რეგულარული გამოსახულებები, რომლებიც აღნიშნავენ P და Q რეგულარულ სიმრავლეს, მაშინ a) (p+q) არის რეგულარული გამოხატულება, რომელიც აღნიშნავს P Q; ბ) pq არის რეგულარული გამოხატულება, რომელიც აღნიშნავს PQ; გ) p* არის P* აღმნიშვნელი რეგულარული გამოხატულება; 5) სხვა არაფერია რეგულარული გამოხატულება.

ძირითადი განმარტებები პრიორიტეტიზაცია: * (გამეორება) – უმაღლესი პრიორიტეტი; შეერთება; + (კავშირი). ასე რომ 0 + 10* = (0 + (1 (0*))). მაგალითები: 1. 01 ნიშნავს (01); 2. 0* - (0*); 3. (0+1)* - (0, 1)*; 4. (0+1)* 011 - ნიშნავს ყველა სტრიქონის სიმრავლეს, რომელიც შედგება 0 და 1-ისგან და მთავრდება 011 სტრიქონით; 5. (a+b) (a+b+0+1)* ნიშნავს ყველა სტრიქონის სიმრავლეს (0, 1, a, b)* დაწყებული a ან b-ით.

ლემის ძირითადი განმარტებები: 1) α + β = β + α 2) * = e 3) α + (β + γ) = (α + β) + γ 4) α (βγ) = (αβ)γ 5 ) α( β + γ) = αβ + αγ 6) (α + β)γ = αγ + βγ 7) αe = eα = α 8) α = 9) α+α* = α* 10) (α*)* = α* 11) α+α = α 12) α+ = α

RT და RM RM კომუნიკაცია არის RT-ის მიერ გენერირებული ენები. მაგალითად: x = a+b, y = c+d, x X = (a, b), y Y = (c, d), x + y X Y = (a, b, c, d). შეერთება: xy XY = (ac, ad, bc, bd). k(u+o)t (k)(u, o)(t) = (ვეშაპი, კატა) ან ლემებით No5 და No6 k(u+o)m = ვეშაპი + კატა (ვეშაპი, კატა) . გამეორება: x = a, x* X* = (e, a, aaa, ...), ანუ x* = e + xxx + …

RT-ისა და RM-ის ურთიერთობა შეერთებისა და შეერთების გამეორება: (xy)* = e + xyxyxy + ... (x + y)* = e + (x + y)(x + y) + ... = = e + xx + xy + yx + yy + xxx + … მაგალითი: 0 + 1(0+1)* (0) ((1) (0, 1)*) = (0, 1, 10, 11, 100, 101, 110, 111 ...). კავშირი კომუტაციურია: x + y = y + x შეერთება არ არის: xy ≠ yx

RT და PM შორის ურთიერთობა პრიორიტეტული მაგალითები: x + yz (x, yz), (x + y)z (xz, yz), x + y* (e, x, y, yyy, yyyy, ...), (x + y)* (e, x, y, xx, xy, yx, yy, xxx, …), (xy)* (e, xyxy, …), xy* (x, xyy, xyyy, …). ახალი ლემები: a* + e = a*; (a + e)* = a*; a*a* = a*; e* = e; და ა.შ.

განტოლებათა რეგულარული სისტემები განტოლება რეგულარული კოეფიციენტებით X = a. X + b აქვს ამონახსნი (უმცირესი ფიქსირებული წერტილი) a*b: aa*b + b = (aa* + e)b = a*b განტოლებათა სისტემა რეგულარული კოეფიციენტებით: X 1 = α 10 + α 11 X 1 + α 12 X 2 + … + α 1 n. Xn X 2 \u003d α 20 + α 21 X 1 + α 22 X 2 + ... + α 2 n. Xn ……………………………. . Xn = αn 0 + αn 1 X 1 + αn 2 X 2 + … + αnn. Xn უცნობი - Δ = (X 1, X 2, …, Xn).

განტოლებათა რეგულარული სისტემები ამოხსნის ალგორითმი (გაუსის მეთოდი): ნაბიჯი 1. დააყენეთ i = 1. ნაბიჯი 2. თუ i = n, გადადით მე-4 საფეხურზე. წინააღმდეგ შემთხვევაში, ჩაწერეთ Xi განტოლებები სახით Xi = αXi + β (β = β 0 + βi +1 Xi+1 + … + βn.Xn). შემდეგ, მარჯვენა მხარეს Xi+1, …, Xn განტოლებისთვის, ჩვენ ვცვლით Xi-ს რეგულარული გამოსახულებით α*β. ნაბიჯი 3. გაზარდეთ i 1-ით და დაუბრუნდით მე-2 საფეხურს. ნაბიჯი 4. ჩაწერეთ Xn-ის განტოლება, როგორც Xn = αXn + β. გადადით მე-5 საფეხურზე (i = n-ით). ნაბიჯი 5. Xi-ს განტოლება არის Xi = αXi + β. გამომავალზე ჩაწერეთ Xi = α*β, განტოლებებში Xi– 1, …, X 1 ჩაანაცვლეთ α*β Xi–ს ნაცვლად. ნაბიჯი 6. თუ i = 1, გააჩერეთ, წინააღმდეგ შემთხვევაში შეამცირეთ i 1-ით და დაუბრუნდით მე-5 საფეხურს.

DFA-ის ტრანსფორმაცია RW-ად DFA M = (Q, Σ, δ, q 0, F) ჩვენ ვქმნით სისტემას რეგულარული კოეფიციენტებით, სადაც Δ = Q: 1. ვაყენებთ αij: = ; 2. თუ δ(Xi, a) = Xj, a Σ, მაშინ αij: = αij + a; 3. თუ Xi F ან δ(Xi,) = HALT, მაშინ αi 0: = e. ამოხსნის შემდეგ სასურველი RV იქნება X 1 = q 0.

DFA-ზე გადაყვანა RW-ზე მაგალითი: ფიქსირებული წერტილის რიცხვისთვის ვიღებთ სისტემას q 0 = + q 0 + კვ 1 + pq 2 + dq 3 + q 4 q 1 = + q 0 + q 1 + pq 2 + dq 3 + q 4 q 2 = + q 0 + q 1 + q 2 + q 3 + dq 4 q 3 = e + q 0 + q 1 + q 2 + dq 3 + pq 4 = e + q 0 + q 1 + q 2 + q 3 + dq 4 აქ: s არის რიცხვის ნიშანი, s = "+" + "-"; p – ათობითი წერტილი, p = ". "; d - რიცხვები, d = "0" + "1" + ... + "9".

DFA-ში RW კონვერტაცია ამოხსნა: q 0 = *(sq 1 + pq 2 + dq 3 + q 4 +) = sq 1 + pq 2 + dq 3 q 1 = + q 0 + q 1 + pq 2 + dq 3 + q 4 = pq 2 + dq 3, q ​​2 = + q 0 + q 1 + q 2 + q 3 + dq 4 = dq 4, q 3 = e + q 0 + q 1 + q 2 + dq 3 + pq 4 = dq 3 + pq 4 + e, q 4 = e + q 0 + q 1 + q 2 + q 3 + dq 4 = dq 4 + e. მესამე განტოლებიდან: q 3 \u003d dq 3 + pq 4 + e \u003d d * (pq 4 + e). მეოთხე განტოლებიდან: q 4 = dq 4 + e = d*.

გადაიყვანეთ DFA RW-ზე უკუ: q 3 = d*(pq 4 + e) ​​= d*(pd* + e), q 2 = dq 4 = dd*, q 1 = pq 2 + dq 3 = pdd* + dd *(pd* + e), q 0 = sq 1 + pq 2 + dq 3 = s(pdd* + dd*(pd* + e)) + pdd* + dd*(pd* + e). ამრიგად, ეს DFA შეესაბამება RE s(pdd* + dd*(pd* + e)) + pdd* + dd*(pd* + e). გასამარტივებლად: s(pdd* + dd*(pd* + e)) + pdd* + dd*(pd* + e) ​​= = spdd* + sdd*(pd* + e) ​​+ pdd* + dd*(pd* + e) ​​= (s + e)(pdd* + dd*(pd* + e)) უფრო მოკლე აღნიშვნისთვის შეგიძლიათ გამოიყენოთ დადებითი გამეორება aa* = a*a = a+: (s + e )(pdd* + dd* (pd* + e)) = (s + e)(pd+ + d+pd* + d+)

DFA-დან RT-ში ტრანსფორმაცია DFA-ზე გადასვლის ფუნქციის გრაფიკის შედგენა ძირითადი რეგულარული გამოხატვის ოპერაციებზე: q 0 a b a q 1 q 2 q 1 q 0 a+b a b ab q 2 a*

DFA-ზე RT-ზე გადაქცევა ოპერაციების უფრო რთული კომბინაციები: q 0 a q 1 b b b q 0 a q 2 q 1 (a + e)b c b q 0 q 2 ab(cab)* q 0 (a + b)* q 0 a q 1 aa* = a+ q 0 a q 1 a b a a (ab)+ q 2 b q 1 c e + (a + b)c*

DFA-ში RW კონვერტაცია RW-სთვის (s + e)(pd+ + d+(pd* + e)): q 0 p q 2 d s p q 1 d d q 3 d p q 4 d q 5 d

რეალურ დროში პროგრამირების რეგულარული გამონათქვამები: ჩაშენებულია პროგრამირების ბევრ ენაში (PHP, Java. Script, ...); დანერგილია დანამატების სახით (მაგალითად, Regex კლასი .NET პლატფორმისთვის). განსხვავებები წერის ფორმებში: x? = x + e x(1, 3) = x + xxx და ა.შ.

RT პროგრამირება Regex კლასის კონსტრუქციები (System.Text.Regular.Expressions): სიმბოლოების გაქცევის თანმიმდევრობის ინტერპრეტაცია b როდესაც გამოიყენება კვადრატულ ფრჩხილებში, შეესაბამება სიმბოლოს "←" (u 0008) t, r, n, a, f, v Tab (u). 0009), ვაგონის დაბრუნება (u 000 D), ახალი ხაზი (u 000 A) და ა.შ. გ. X საკონტროლო სიმბოლო (მაგ. c. C არის Ctrl+C, u 0003) e Escape (u 001 B) ooo Octal ASCII სიმბოლო xhh Hex ASCII სიმბოლო uhhhh Unicode სიმბოლო შემდეგი სიმბოლო არ არის სპეციალური PB სიმბოლო. ყველა სპეციალური სიმბოლო უნდა იყოს ამოღებული ამ სიმბოლოთი. მაგალითი (მაგალითში მოცემულია ნიმუში და საძიებო სტრიქონი, ხაზგასმულია სტრიქონში ნაპოვნი შესატყვისები): @"rnw+" – "rn. აქ არის n ორი სტრიქონი" .

პროგრამირება RT სიმბოლოების ქვეჯგუფები. ნებისმიერი სიმბოლო, გარდა სტრიქონის დასასრულისა (n) ნებისმიერი სიმბოლო სიმრავლიდან [^xxx] ნებისმიერი სიმბოლო, გარდა სიმბოლოების ნაკრებიდან ნებისმიერი სიმბოლო დიაპაზონიდან ] ერთი სიმრავლის ან დიაპაზონის გამოკლება სხვა p(სახელი) ნებისმიერი მითითებული სიმბოლო უნიკოდის კატეგორიის მიხედვით სახელი P (სახელი) ნებისმიერი სიმბოლო, გარდა უნიკოდის კატეგორიის მიერ მითითებული სახელისა w სიმბოლოების ნაკრები, რომლებიც გამოიყენება იდენტიფიკატორების მითითებისას W სიმბოლოების ნაკრები არ გამოიყენება იდენტიფიკატორების მითითებისას s სივრცეები S ყველაფერი, გარდა სივრცეებისა d ციფრები D არა ციფრები მაგალითები : @". +" – "rn. აქ არის n ორი ხაზი"; @"+" - "0xabcfx"; @"[^fx]+" – "0 xabcfx"; @"+" - "0xabcfx"; @"[^a-f]+" – "0 xabcfx"; @"]+" – "0xabcfx"; @"p(Lu)" - "ქალაქის განათება"; // Lu - დიდი ასოები @"P(Lu)" - "ქალაქი"; @"p(Is. Cyrillic)" - "ha. OS"; // არის. კირილიცა - რუსული ასოები

PB პროგრამირების წამყვანი ^, A სტრიქონის დასაწყისში $, Z სტრიქონის ბოლოს ან "n"-მდე სტრიქონის ბოლოს z სტრიქონის ბოლოს G სადაც დასრულდა წინა მატჩი b სიტყვის საზღვარი B ნებისმიერი პოზიცია, რომელიც არ არის სიტყვის საზღვარზე მაგალითები: @ "G(d)" - "(1)(3)(5)(9)"; // სამი მატჩი (1), (2) და (3) @"bnS*ionb" – "ერის შემოწირულობა"; @"Bendw*b" – "ბოლო აგზავნის გამძლე კრედიტორს".

RT ოპერაციების პროგრამირება (რაოდენობები) *, *? გამეორება +, +? პოზიტიური გამეორება? , ? ? ნული თუ ერთი მატჩი (n), (n)? ზუსტად n ემთხვევა (n, ), (n, )? მინიმუმ n მატჩი (n, m), (n, m)? n-დან m-მდე ემთხვევა მაგალითები (პირველი კვანტიფიკატორები ხარბები არიან, ეძებენ რაც შეიძლება მეტ ელემენტს, მეორეები ზარმაცები არიან, ეძებენ რაც შეიძლება ნაკლებ ელემენტს): @"d(3, )" – "888 -5555"; @"^d(3)" - "913 -913"; @"-d(3)$" - "913 -913"; @"5+? 5" - "888 -5555"; // სამი მატჩი - 55, 55 და 55 @"5+5" - "888 -5555".

RT პროგრამირების დაჯგუფება () ჯგუფს ავტომატურად ენიჭება ნომერი (?:) არ შეინახოთ ჯგუფი (?) ან (? "სახელი") თუ მატჩი იპოვეს, შექმენით დასახელებული ჯგუფი (?) ან წაშალეთ ადრე განსაზღვრული ჯგუფი და (? "name-name") ინახავს ახალ ჯგუფში ქვესტრიქონს ადრე განსაზღვრულ ჯგუფსა და ახალ ჯგუფს შორის (? imnsx:) რთავს ან გამორთავს ჯგუფში ხუთი (? -imnsx:) შესაძლო ვარიანტებიდან რომელიმეს: i - case. უგრძნობი; s არის ერთი ხაზი (მაშინ „.“ არის ნებისმიერი სიმბოლო); m – მრავალხაზოვანი რეჟიმი (“^”, “$” – თითოეული სტრიქონის დასაწყისი და დასასრული); n - არ დაიჭიროთ უსახელო ჯგუფები; x - გამორიცხეთ შაბლონიდან შეუცვლელი სივრცეები და ჩართეთ კომენტარები რიცხვის ნიშნის შემდეგ (#) (?=) ნულოვანი სიგრძის პოზიტიური განხილვის მტკიცება

RE პროგრამირება (? !) ნულოვანი სიგრძის ნეგატიური მტკიცება (?) გამოთქმის არადაბრუნებული (ხარბი) ნაწილი მაგალითები: @"(an)+" – "bananas annals"; @"an+" – "ბანანის ანალები"; // შედარება, სამი მატჩი - an, an და ann @"(? i: an)+" - "ba. NAnas annals"; @"+(? =d)" – "abc xyz 12 555 w"; @"(?

Src="https://website/presentation/-112203859_437213351/image-24.jpg" alt="(!LANG:Programming RT მითითების ნომერი ჯგუფის მითითება k დასახელებული ჯგუფის მითითება მაგალითები: @"> Программирование РВ Ссылки число Ссылка на группу k Ссылка на именованную группу Примеры: @"(w)1" – "deep"; @"(? w)k " – "deep". Конструкции изменения | Альтернатива (соответствует операции объединения) (? (выражение)да|нет) Сопоставляется с частью «да» , если выражение соответствует; в противном случае сопоставляется с необязательной частью «нет» (? (имя)да|нет), Сопоставляется с частью «да» , если названное имя (? (число)да|нет) захвата имеет соответствие; в противном случае сопоставляется с необязательной частью «нет» Пример: @"th(e|is|at)" – "this is the day";!}

RT პროგრამირების ჩანაცვლება $number ცვლის სტრიქონის ნაწილს, რომელიც შეესაბამება ჯგუფს მითითებული ნომრით $(სახელი) ანაცვლებს ჯგუფის შესაბამისი სტრიქონის ნაწილს მითითებული სახელით $$ შემცვლელი $$& ჩანაცვლება სრულის ასლით match $` შეცვალეთ შეყვანის სტრიქონის ტექსტი სანამ არ დაემთხვა $" შეცვალეთ შეყვანის ხაზის ტექსტი მატჩის შემდეგ $+ შეცვალეთ ბოლო დაჭერილი ჯგუფი $_ ჩაანაცვლეთ მთელი ხაზი კომენტარები (? #) ხაზოვანი კომენტარი # კომენტარი ხაზის ბოლოს

RT პროგრამირების შედეგები Regex: Regex Matches() Match. Collection Match Groups() ჯგუფი. Collection Group Captures() Capture. Collection Captures()

RT პროგრამირების მაგალითი C++ CLI-ში (Visual C++/CLR/CLR კონსოლის აპლიკაცია): int main() ( Regex ^r = gcnew Regex(L"((\d)+)+"); Match ^m = r-> Match (L"123 456"); int მატჩი. რაოდენობა = 0; while (m->წარმატება) ( კონსოლი: : ჩაწერა. ხაზი (L"Match(0)", ++შემთხვევა. რაოდენობა); for (int i = 1; i ჯგუფები-> რაოდენობა; i++) ( ჯგუფი ^g = m->ჯგუფები[i]; კონსოლი: : ჩაწერა. Line(L" ჯგუფი (0) = "(1)"", i, g-> მნიშვნელობა ); for (int j = 0; j Captures->Count; j++) (Capture ^c = g->Captures[j]; Console: : Write.Line(L" Capture(0) = "(1)" , პოზიცია = (2), სიგრძე = (3)", j, c, c->ინდექსი, c->სიგრძე); ) ) m = m->შემდეგი. Match(); ) return 0; ) სისტემა: : ტექსტი : : რეგულარული. გამონათქვამები

მოქმედებების ჩართვა და შეცდომების ძიება რიცხვში მნიშვნელოვანი ციფრების რაოდენობის შეზღუდვა: (s + e)(pd+ + d+(pd* + e)) s = +|p = . d = ds + e = s? = (+|-)? pd* + e = (pd*)? =(.დ*)? @"(+|-)? (. d+|d+(. d*)?)" ან @"^(+|-)? (. d+|d+(. d*)?)$" Regex r = ახალი რეგექსი (@"^(+|-)? (. (? "ციფრი"დ)+|(? "ციფრი"დ)+(. (? "ციფრი"დ)*)?)$"); ემთხვევა m = r. მატჩი ("+1. 23456789"); if (მ. წარმატება) ( ჯგუფი g = m. ჯგუფები["ციფრი"]; თუ (გ. გადაღებები. რაოდენობა

მოქმედებების ჩართვა და შეცდომების პოვნა შეცდომის პოზიციის განსაზღვრა: Regex r = new Regex(@"(+|-)? (. (? "ციფრი"d)+|(? "ციფრი"d)+(. (? " ციფრი"d )*)?)"); string str = "+1.2345!678"; ემთხვევა m = r. Match(str); if (მ. წარმატება) ( ჯგუფი g = m. ჯგუფები["ციფრი"]; if (გ. გადაღებები. რაოდენობა 0) კონსოლი. ჩაწერა. ხაზი ("შეცდომა 1 პოზიციაზე: მოულოდნელი სიმბოლო "(0)"", str. სხვა შემთხვევაში, თუ (მ. სიგრძე

მოქმედებების ჩართვა და შეცდომების ძიება შეცდომის პოზიციის განსაზღვრა: 1. შეყვანის სტრიქონის პირველი პოზიცია (1), თუ პირველი მატჩი არ იწყება პოზიციიდან Index = 0; 2. პოზიცია ბოლო მატჩის შემდეგ (შემთხვევა. სიგრძე + 1), თუ ის არ ემთხვევა შეყვანის სტრიქონის ბოლო პოზიციას; 3. პირველი შესვენების პოზიცია მატჩებს შორის (მატჩი[i]. ინდექსი + შესატყვისი[i]. სიგრძე + 1), თუ წინა მატჩის შემდგომი სიმბოლო არ არის შემდეგი მატჩის პირველი სიმბოლო.

ინდექსი) შესვენება; ინდექსი = m[i]. ინდექსი + m[i]. სიგრძე; ) კონსოლი. დაწერე. Line("შეცდომა პოზიციაზე (0) "(1)"", ინდექსი + 1, str); ) "abc. xyz. pqr" სწორია; + abc. xyz. pqr" - შეცდომა პოზიცია 1 ("+"); "abc. xyz. pqr!" – შეცდომა 12 პოზიციაზე (“!”); "abc. xyz!. pqr" - შეცდომა 8 პოზიციაზე ("!").

მოქმედებების ჩართვა და შეცდომების ძიება მაგრამ! "abc. xyz. +pqr" - შეცდომა 8 პოზიციაზე (". "). ახალი ნიმუშის ვარიანტი: @"w+(. w+)*(. (? !$))? " ვალიდაცია: "abc. xyz. +pqr" - შეცდომა 9 პოზიციაზე ("+"); "abc. xyz. pqr. "- შეცდომა 12 პოზიციაზე (". ").

დაბალანსებული განმარტებები: "(? "x")" ამატებს ერთ ელემენტს კოლექციას სახელად "x"; "(? "-x")" შლის ერთ ელემენტს კრებულიდან "x"; "(? (x)(? !))" ამოწმებს, რომ "x" კრებულში ელემენტები არ არის დარჩენილი. ენა L, რომელიც აღწერს პასკალური ენის ჩადგმულ განცხადებებს „დაწყება დასასრული; ': @"^s*((? "იწყება+)+(? "-დაწყება"მთავრდება*; s*)+)*(? (დაიწყება)(? !))$".

DFA არის NFA-ს განსაკუთრებული შემთხვევა. მასში:

არ არსებობს ε-გადასვლებით მდგომარეობა;

თითოეული მდგომარეობის S და შეყვანის სიმბოლო a, არის მაქსიმუმ ერთი რკალი გამავალი S-დან და იარლიყით a.

DFA-ს აქვს მაქსიმუმ ერთი გადასვლა ნებისმიერი შეყვანის სიმბოლოსთვის თითოეული მდგომარეობიდან. თუ ცხრილი გამოიყენება DFA გადასვლის ფუნქციის წარმოსაჩენად, მაშინ თითოეული ჩანაწერი შეიცავს მხოლოდ ერთ მდგომარეობას. ამრიგად, ადვილია იმის შემოწმება, იძლევა თუ არა მოცემული DFA განსაზღვრულ მწკრივს, ვინაიდან დაწყების მდგომარეობიდან მხოლოდ ერთი გზაა, რომელიც ამ მწკრივით არის მონიშნული.

სურათი 3 გვიჩვენებს DFA გადასვლის გრაფიკს, რომელიც იძლევა იმავე ენას (a|b) *a(a|b)(a|b), როგორც NFA სურათზე 1.

სურათი 3. DFA, რომელიც საშუალებას აძლევს სტრიქონს (a|b) * a(a|b)(a|b).

დეტერმინისტული სასრული ავტომატი M, რომელიც იღებს მოცემულ ენას:

M = ((1, 2, 3, 4, 5, 6, 7, 8), (a, b), D, 1, (3, 5, 6, 8))

გადასვლის ფუნქცია D განისაზღვრება შემდეგნაირად:

nc-ის აგება რეგულარული გამოსახულებიდან

1. ε-სთვის NFA-ს აქვს შემდეგი ფორმა (0 არის საწყისი მდგომარეობა, 1 არის საბოლოო მდგომარეობა):

2. მოცემულ NFA ენაში ჩართულისთვის:

3. მოდით, N(s) და N(t) იყოს NFA რეგულარული გამოსახულებების s და t.

რეგულარული გამოსახულებისთვის s|t, კომპოზიტურ NFA-ს აქვს შემდეგი ფორმა:

ბ. რეგულარული გამოხატვისთვის st NFA:

თან. გამოხატვისთვის s*, NFA-ს აქვს ფორმა:

დ. ფრჩხილებში (s) გამოსახულებისთვის გამოიყენება NFA N(s) როგორც ა პუნქტში.

ყოველი ახალი სახელმწიფო იღებს ინდივიდუალურ სახელს. NFA N(r)-ის კონსტრუქციას აქვს შემდეგი თვისებები:

N(r) აქვს რამდენიმე მდგომარეობა, რომელიც არ აღემატება სიმბოლოების რაოდენობას 2-ჯერ მეტით.

N(r) აქვს ზუსტად ერთი საწყისი და ერთი საბოლოო მდგომარეობა. საბოლოო მდგომარეობას არ აქვს გამავალი გადასვლები.

თითოეულ N(r) მდგომარეობას აქვს ან 1 გადასვლის სიმბოლო ანბანიდან (), ან არაუმეტეს 2 გამავალი ε-გადასვლისა.

ნა დკა-ში გადაყვანა.

NFA სურათზე 1 აქვს 2 გადასვლა 0 მდგომარეობიდან a სიმბოლოსთვის: მდგომარეობს 0 და 1. ასეთი გადასვლა ბუნდოვანია, ისევე როგორც ε-ში გადასვლა. ასეთი NSC-ების მოდელირება კომპიუტერული პროგრამის დახმარებით გაცილებით რთულია. დასაშვებობის განმარტებაში ნათქვამია, რომ უნდა არსებობდეს გარკვეული გზა საწყისი მდგომარეობიდან საბოლოო მდგომარეობამდე, მაგრამ როდესაც არსებობს მრავალი ბილიკი ერთიდაიგივე შეყვანის სტრიქონისთვის, ყველა მათგანი უნდა იყოს გათვალისწინებული საბოლოო მდგომარეობისკენ მიმავალი გზის მოსაძებნად ან გასარკვევად. რომ ასეთი გზა არ არსებობს.

NFA გარდამავალ ცხრილში, თითოეული ჩანაწერი შეესაბამება მდგომარეობების ერთობლიობას, ხოლო DFA გარდამავალ ცხრილში - მხოლოდ ერთს. ტრანსფორმაციის არსი მდგომარეობს იმაში, რომ DFA-ის თითოეული მდგომარეობა შეესაბამება NFA-ს მდგომარეობების სიმრავლეს. DFA იყენებს თავის მდგომარეობას, რათა თვალყური ადევნოს ყველა შესაძლო მდგომარეობას, რომელშიც NFA შეიძლება იყოს შემდეგი შეყვანის სიმბოლოს წაკითხვის შემდეგ. ანუ, შეყვანის ნაკადის წაკითხვის შემდეგ, DFA არის ისეთ მდგომარეობაში, რომელიც წარმოადგენს NFA მდგომარეობების გარკვეულ კომპლექტს, რომლებიც ხელმისაწვდომია საწყისიდან შეყვანის სტრიქონის შესაბამისი ბილიკის გასწვრივ. DFA-ს ასეთი მდგომარეობების რაოდენობა შეიძლება მნიშვნელოვნად აღემატებოდეს NFA-ს ქვეყნების რაოდენობას (ექსპონენციალური დამოკიდებულება), მაგრამ პრაქტიკაში ეს ძალზე იშვიათია და ზოგჯერ DFA-ში კიდევ უფრო ნაკლები მდგომარეობაა, ვიდრე NFA-ში.

განვიხილოთ ასეთი ტრანსფორმაცია კონკრეტული მაგალითის გამოყენებით. სურათი 4 გვიჩვენებს სხვა NFA, რომელიც საშუალებას აძლევს ენას (a|b) *a(a|b)(a|b) (როგორც სურათებში 1 და 3).

სურათი 4. NFA, რომელიც საშუალებას აძლევს ენას (a|b) * a(a|b)(a|b)

სურათზე გამოსახული 13 მდგომარეობიდან მე-14 მდგომარეობაზე გადასვლა შეიძლება წარმოდგენილი იყოს 8 მდგომარეობიდან მე-13 მდგომარეობაზე გადასვლის მსგავსად.

მოდით ავაშენოთ DFA მოცემული ენისთვის. ეკვივალენტური DFA-ს საწყისი მდგომარეობა არის მდგომარეობა A =(0, 1, 2, 4, 7), ანუ ის მდგომარეობები, რომელთა მიღწევაც შესაძლებელია 0-დან ε-მდე.

შეყვანის სიმბოლოს ანბანი არის (a, b). საწყისი მდგომარეობიდან A შეიძლება გამოვთვალოთ მისაწვდომი მდგომარეობა a-სთან მიმართებაში. მოდით ვუწოდოთ ამ მდგომარეობას B = (1, 2, 3, 4, 6, 7, 8, 9, 11, 13, 14).

A-ში არსებულ მდგომარეობებს შორის მხოლოდ მე-4 მდგომარეობას აქვს გადასვლა b-ზე მე-5 მდგომარეობაზე, ამიტომ DFA-ს აქვს გადასვლა b-ზე A-დან C = (1, 2, 4, 5, 6, 7) მდგომარეობაზე.

თუ ამ პროცესს გავაგრძელებთ B და C მდგომარეობებით, NFA მდგომარეობების ყველა ნაკრები იქნება მარკირებული. ამრიგად, ჩვენ გვექნება მდგომარეობების ნაკრები:

A = (0, 1, 2, 4, 7)

B = (1, 2, 3, 4, 6, 7, 8, 9, 11, 13, 14)

C = (1, 2, 4, 5, 6, 7)

D = (10, 12, 13, 14)

მდგომარეობა A არის საწყისი, ხოლო მდგომარეობები B, D, E არის საბოლოო.

სრული გარდამავალი ცხრილი ნაჩვენებია ქვემოთ.

ქვემოთ მოყვანილი სურათი 5 გვიჩვენებს თავად DFA ამ ენისთვის.

სურათი 5. DFA, რომელიც იღებს ენას (a|b) *a(a|b)(a|b)

გამოყენებული ლიტერატურის სია:

Pentus A. E., Pentus M. R. – ფორმალური ენების თეორია

A. Aho, R. Seti, D. Ullman - შემდგენელები: პრინციპები, ტექნოლოგიები, ინსტრუმენტები.

დეტერმინისტული სასრული ავტომატის აგება რეგულარული გამოსახულებიდან

მოდით ახლა წარმოგიდგინოთ ალგორითმი დეტერმინისტული სასრული ავტომატის ასაგებად რეგულარული გამოსახულებიდან, რომელიც საშუალებას აძლევს იმავე ენას [?].

თ ანბანში მოყვანილი იყოს რეგულარული გამოხატულება r. რეგულარულ გამოსახულებას r: (r)# დაუმატეთ ბოლო მარკერი. ასეთ რეგულარულ გამონათქვამს დასრულებული ეწოდება. მუშაობის პროცესში ალგორითმი გამოიყენებს დასრულებულ რეგულარულ გამოხატვას.

ალგორითმი იმუშავებს სინტაქსურ ხეზე დასრულებული რეგულარული გამოსახულებისთვის (r)#, რომლის თითოეული ფურცელი მონიშნულია სიმბოლოთი და თითოეული შიდა ზედააღინიშნება ერთ-ერთი ოპერაციის ნიშნით: (შეერთება),| (კავშირი), * (გამეორება).

ხის თითოეულ ფოთოლს (ელექტრონული ფოთლების გარდა) მიენიჭება უნიკალური ნომერი, რომელსაც ეწოდება პოზიცია, და ჩვენ მას გამოვიყენებთ, ერთის მხრივ, ხის ფოთლის მითითებისთვის და, მეორე მხრივ, აღსანიშნავად. ამ ფოთლის შესაბამის სიმბოლოს. გაითვალისწინეთ, რომ თუ სიმბოლო მრავალჯერ გამოიყენება ჩვეულებრივ გამოსახულებაში, მას აქვს მრავალი პოზიცია.

მოდით გადავხედოთ T ხეს ქვემოდან ზემოდან მარცხნიდან მარჯვნივ და გამოვთვალოთ ოთხი ფუნქცია: nullable, firstpos, lastpos და followpos. პირველი სამი ფუნქცია - nullable, firstpos და lastpos - განისაზღვრება ხის კვანძებზე, ხოლო followpos განისაზღვრება პოზიციების სიმრავლეზე. ყველა ფუნქციის მნიშვნელობა, გარდა nullable არის პოზიციების სიმრავლე. Followpos ფუნქცია გამოითვლება დანარჩენი სამი ფუნქციის მეშვეობით.

ფუნქცია firstpos(n) რეგულარული გამოხატვის სინტაქსის ხის თითოეული n კვანძისთვის იძლევა პოზიციების ერთობლიობას, რომლებიც ემთხვევა პირველ სიმბოლოებს ქვესტრიქონები, გენერირებული n წვეროზე ქვეგამოხატვით. ანალოგიურად, lastpos(n) იძლევა პოზიციების სიმრავლეს, რომელიც შეესაბამება ბოლო სიმბოლოებს ქვესტრიქონებიგენერირებული n წვეროთი ქვეგამოხატებით. n კვანძისთვის, რომლის ქვეხეებს (ანუ ხეებს, რომელთა ძირი კვანძი n არის) შეუძლიათ შექმნან null სიტყვა, განსაზღვრეთ nullable(n)=true, ხოლო დანარჩენი კვანძებისთვის nullable(n)=false.

nullable, firstpos და lastpos ფუნქციების გამოსათვლელი ცხრილი ნაჩვენებია ნახ. 3.11.

მაგალითი 3.7.ნახ. 3.12 გვიჩვენებს სინტაქსის ხეს დასრულებული რეგულარული გამოსახულებისთვის (a|b) * abb# პირველიpos და lastpos ფუნქციების შეფასების შედეგით. თითოეული კვანძის მარცხნივ არის firstpos-ის მნიშვნელობა, კვანძის მარჯვნივ არის lastpos-ის მნიშვნელობა. გაითვალისწინეთ, რომ ეს ფუნქციები შეიძლება გამოითვალოს ერთ ხეზე გადასასვლელად.

თუ i არის პოზიცია, მაშინ followpos(i) არის j პოზიციების ერთობლიობა, რომ არის რაღაც სტრიქონი... cd ..., რომელიც გვხვდება ნორმალურ გამონათქვამში აღწერილ ენაში, რომ i პოზიცია ემთხვევა c და პოზიციას. j არის ჩანაწერი d.

ბრინჯი. 3.11.

ბრინჯი. 3.12.

Followpos ფუნქცია ასევე შეიძლება გამოითვალოს ხის ერთი ქვემოდან ზევით გადაკვეთისას ამ ორი წესის მიხედვით.

1. მოდით n იყოს შიდა კვანძი მოქმედებით (შეერთება), u და v მისი შთამომავლები. შემდეგ თითოეული პოზიციისთვის, რომელიც i ჩართულია lastpos(u)-ში, ჩვენ ვუმატებთ followpos(i) სიდიდეების სიმრავლეს firstpos(v).

2. მოდით n იყოს შიდა კვანძი ოპერაციით * (იტერაცია), u - მისი შთამომავალი. შემდეგ თითოეული პოზიციისთვის, რომელიც i ჩართულია lastpos(u)-ში, ჩვენ ვუმატებთ followpos(i) სიმრავლეს firstpos(u).

მაგალითი 3.8. წინა მაგალითიდან რეგულარული გამოხატვისთვის followpos ფუნქციის შეფასების შედეგი ნაჩვენებია ნახ. 3.13.

ალგორითმი 3.3. DFA-ს პირდაპირი კონსტრუქცია რეგულარული გამოხატულებიდან.

შესასვლელი. რეგულარული გამოთქმა r ანბანში T.

გამომავალი. DFA M = (Q, T, D, q 0, F) ისეთი, რომ L(M) = L(r).

მეთოდი. DFA ქვეყნები შეესაბამება პოზიციების კომპლექტს.

თავდაპირველად Q და D ცარიელია. მიჰყევით ნაბიჯებს 1-6:

(1) შექმენით სინტაქსის ხე გაფართოებული რეგულარული გამოსახულებისთვის (r)#.