שפה אונארית

תבנית:מקורות שפה אונארית היא שפה שמכילה רק מילים מהצורה $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, כולל שפות אונאריות לא כריעות.

קישורים חיצוניים

• תבנית:אקדמיה