Содержание
- 2. Saturs Ievads Baložu ligzdas princips (Dirihlē princips) Pumpējošā lemma
- 3. Regulāras valodas Neregulāras valodas
- 4. Kā mēs varam pierādīt, ka valoda L nav regulāra? Jāpierāda, ka neeksistē DFA, kas akceptē L.
- 5. Baložu ligzdas princips
- 6. baloži baložu ligzdas
- 7. Vienā baložu ligzdā būs 2 baloži
- 8. ........... ........... baloži baložu ligzdas
- 9. Baložu ligzdas princips ........... baloži baložu ligzdas Būs vismaz viena ligzda ar 2 baložiem
- 10. Baložu ligzdas princips un DFA
- 11. Ja dots DFA ar 4 stāvokļiem DFA ar 4 stāvokļiem
- 12. Virknes ceļš: stāvokļi neatkārtojas
- 13. Virknes ceļš: stāvokļi atkārtojas Virknes ceļš:
- 14. Ja virkne w, kuras garums : tādejādi stāvokļi sāks atkārtoties. tad pāreju šai virknei būs vairāk
- 15. Jebkuram DFA: Virkne w, kuras garums stāvokļu skaits Stāvoklim q nāksies atkārtoties virknes w ceļā. ......
- 16. Citiem vārdiem virknei : pārejas ir baloži stāvokļi ir baložu ligzdas ...... ...... ceļš Stāvoklis, kurš
- 17. Pumpējošā lemma
- 18. Paņemsim neierobežotu valodu L. Eksistē DFA, kurš akceptē valodu L stāvokļi
- 19. Paņemsim virkni w, kura Te parādīts ceļš, kurš tiek veikts apskatot virkni w ......... walk
- 20. Ja virkne w, kuras garums (DFA stāvokļu skaits) tad, pēc baložu ligzdas principa: ceļā w stāvoklis
- 21. ...... ...... ceļš Pieņemsim, ka q ir pirmais stāvoklis, kurš sāk atkārtoties w ceļā
- 22. Uzrakstīsim ...... ......
- 23. ...... ...... Pie tam: garums DFA stāvokļu skaits garums
- 24. virkne ir akceptējama ...... ...... Pie tam:
- 25. virkne ir akceptējama ...... ...... Ievērosim, ka:
- 26. Virkne ir akceptējama ...... ...... Ievērosim, ka:
- 27. virkne ir akceptējama Vispārīgā gadījumā: ...... ......
- 28. ...... ...... Valoda, kuru akceptē DFA Vispārīgā gadījumā:
- 29. Citiem vārdiem, esam aprakstījuši: Pumpējošo lemmu !!!
- 30. Pumpējošā lemma Ņemot neierobežotu regulāru valodu L eksistē konstante m, kurai jebkurai virknei ar garumu mēs
- 31. Piemērs w = ababaa
- 32. Pumpējošās lemmas izmantošana
- 33. Teorēma: Valoda nav regulāra Pierādījums: Izmanto Pumpējošo lemmu
- 34. Pieņemsim pretējo, ka L ir regulāra valoda Tā kā L ir neierobežota mēs varam izmantot Pumpējošo
- 35. Pumpējošā lemmā m ir vesels skaitlis Izvēlēsimies virkni w, tādu, ka garums Pieņemsim
- 36. izriet, ka No Pumpējošās lemmas Rakstām: tādējādi:
- 37. No Pumpējošās lemmas Pretruna!!!
- 40. Mūsu pieņēmums, ka valoda L ir regulāra ir nepareizs. Slēdziens: Ir neregulāra valoda Tādēļ:
- 41. Regulāras valodas Neregulāras valodas
- 42. Uzdevumi Pierādīt, ka valodas ir neregulāras:
- 43. Pieņemsim pretējo, ka šī valoda ir regulāra. Tad ir spēkā Pumpējošā lemma – eksistē fiksēta konstante
- 44. Pieņemsim pretējo, ka šī valoda ir regulāra. Tad ir spēkā Pumpējošā lemma – eksistē fiksēta konstante
- 46. Скачать презентацию