PDA

צפה בגרסה המלאה : [דיון] קביעת רגולריות לשפות



alex200815
11-05-2012, 20:53
http://latex.codecogs.com/gif.latex?L1=%28%7Ba%5Enb%5E%7Bn-1%7D%7D%7Cn%5Cgeq%201%29
http://latex.codecogs.com/gif.latex?L2=%28a%5Enb%5Ek%7Cn%5Cgeq%200,k%5Cgeq%2 00%29
שארית חלוקה של n ב 2 שונה משארית חלוקה של k ב- 2
http://latex.codecogs.com/gif.latex?L3=%28a%5Ekb%5E%7B2m%7D%7Ck%5Cgeq%200,m% 5Cgeq%200%29

קבע אם השפה רגולרית או לא . אם לא נמק .

odp
11-05-2012, 22:44
רק הראשונה אינה רגולרית. תנסה לחשוב למה.

exzoty
11-05-2012, 22:58
הראשונה אינה ריגולרית משום שיש תלות מניה בלתי מוגבלת בחזקות - מספר הbים חייב להיות מספר הaים פחות אחד .

alex200815
13-05-2012, 00:03
בשפה הראשונה האוטומט יצטרך לזכור עד אינסוף כמות אותיות a וכמות אותיות b היות ולהם אותו n מה שאומר שצריך זיכרון לא מוגבל מה שמונע מאוטומט סופי דטרמניסטי לבנות את השפה ולכן היא אינה רגולרית ?
זה כל ההסבר שאני צריך להביא ?

odp
13-05-2012, 00:35
בשפה הראשונה האוטומט יצטרך לזכור עד אינסוף כמות אותיות a וכמות אותיות b היות ולהם אותו n מה שאומר שצריך זיכרון לא מוגבל מה שמונע מאוטומט סופי דטרמניסטי לבנות את השפה ולכן היא אינה רגולרית ?
זה כל ההסבר שאני צריך להביא ?

אין להם את אותו ה-n. ל-a יש n ול-b יש n-1.
חוץ מזה, אני לא יודע איך מלמדים את הנושא בבית הספר, אז אני לא יודע איך הם מצפים שתוכיחו אי רגולריות.