» נושאי לימוד
» נושאי לימוד
יום שבת 4 באפריל 2020
הכרעת שפות
דף ראשי  מכונת טיורינג  הכרעת שפות גרסה להדפסה

הכרעת שפות

 

הגדרה: יהי   S1 א"ב כך  ש: 1S Ï #   ותהיL Í S1   שפה.

תהי  S,h),(Q,S,d M=  מכונת טיורינג. נאמר כי M  מכריעה את L  את לכל wÎS1*  מתקיים:

  ( s , # w #)|-----( h , # 1 # )                                    אם  wÎ L         

                                    ) # o  ( s , # w #)|-----( h , # אם   wÏ L     

כלומר, אם מילה נמצאת בשפה, המכונה תחזיר 1 , אחרת היא תחזיר 0.

 

 

 22-03-04 / 10:59  עודכן ,  31-12-03 / 21:21  נוצר ע"י שמרית דויטש  בתאריך 
 חישוב פונקציה עם K פרמטרים - הקודםהבא - מכונה עם K סרטים 
תגובות הקוראים    תגובות  -  0
דרכונט
מהי מערכת הדרכונט?
אינך מחובר, להתחברות:
דוא"ל
ססמא
נושאי לימוד
חיפוש  |  לא פועל
משלנו  |  לא פועל
גולשים מקוונים: 5