PDA

צפה בגרסה המלאה : הוכחת אי רגולריות - מודלים חישוביים



han98
13-02-2012, 22:03
שלום,מישהו יכול בבקשה לכתוב איך מוכיחים אי רגולריות של:

22082

תודה

Oriel90
29-02-2012, 22:42
w1=a^n
w2=a^j

i לא שווה ל- j

w3= b^m c^k

עבור w1w3 מתקבלת מילה בשפה אך עבור w2w3 לא מתקבלת מילה בשפה, לכן השפה אי רגולרית ע"פ דרך השלילה

shelli
10-04-2015, 13:49
היי אני צריכה לכתוב אם שפה רגולרית/ לא רגולרית והאם היא חופשית הקשר או לא.
אשמח לעזרה!

L_{1}={a^{n}b^{2n}a^{m}

(L_{2}=a^{2n}b^{m}a^{k} (n,m\geq 0, k=m%2

L_{3}=W

w- אורך מילה זוגי

L_{4}=W^{j}

j>0

w=(a^{x}b^{^{y}})
x,y\geq 0