שפה אונארית

שפה אונארית היא שפה שמכילה רק מילים מהצורה $1^{n}$, כלומר שפה L תיקרא אונארית אם $x\in L\ \Rightarrow x=1^{k}$, כאשר 1 יכול להיות כל תו בא"ב סופי. (למרות שמקובל לדבר על א"ב של 0 ו-1 בלבד).

לדוגמה: השפה של כל המחרוזות שמייצגות את המספרים $2^{m}-1$ הראשוניים מעל א"ב של {0,1} היא שפה אונארית.

לכל שפה ניתן להגדיר שפה אונארית מקבילה, כאשר פשוט "מותחים" כל מילה לייצוג אונארי. דוגמה: המילה 1001 (9 בבינארית) תימתח למילה 111111111 (9 פעמים 1).

שפה שניתנת להכרעה בזמן אקספוננציאלי, המקבילה האונרית שלה ניתן להכרעה בזמן ליניארי, אך שפה שאינה כריעה בגרסה הרגילה שלה, אינה כריעה גם בגרסה האונארית. כל שפה אונארית נמצאת ב-P/Poly, כולל שפות אונאריות לא כריעות.

ערך זה הוא קצרמר בנושא מדעי המחשב. אתם מוזמנים לתרום למכלול ולהרחיב אותו.

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

36081984שפה אונארית