PDA

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



david11
03-01-2014, 14:18
שלום, אני חדש בנושא הזה, אשמח אם תדגימו לי איך עושים את השאלה הבאה-



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

chenkop
19-03-2014, 00:25
יש לך שתי דרכים עיקריות להוכיח רגולריות:
1.לבנות אוטומט סופי דטרמיניסטי מלא לשפה.
2.לחלק את השפה לשתי תת שפות, לבנות לכל אחת מהן אוטומט ולהגיד שעפ"י חוקי סגירות השפות הרגולריות השפה L שפה רגולרית כי היא איחוד של שתי השפות...

chenkop
18-07-2015, 13:24
יש לך שתי דרכים עיקריות להוכיח רגולריות:
1.לבנות אוטומט סופי דטרמיניסטי מלא לשפה.
2.לחלק את השפה לשתי תת שפות, לבנות לכל אחת מהן אוטומט ולהגיד שעפ"י חוקי סגירות השפות הרגולריות השפה L שפה רגולרית כי היא איחוד של שתי השפות...
לא בהכרח איחוד... זה יכול להיות משלים,שרשור,היפוך,איחוד וחיתוך שמשפחת השפות הרגולריות סגורות תחתן..
במקרה הזה, כמובן שקל להוכיח באמצעות בניית אס"ד (אוטומט סופי דטרמיניסטי).. והוא:36593
כלומר, מצב אחד מקבל (והתחלתי כמובן..) עם לולאה עצמית עם כל הא"ב הנתון..