תורת האוטומטים - מונחים

מתוך המכלול, האנציקלופדיה היהודית
קפיצה לניווט קפיצה לחיפוש

תורת האוטומטים היא ענף בחישוביות העוסק בחקר מודלים מתמטיים כדוגמת האוטומט הסופי ואוטומט המחסנית.

מושגי יסוד

  • א"ב פורמלי: קבוצה סופית של סימנים ("אותיות").
  • מילה פורמלית: סדרה סופית של אותיות השייכות לא"ב הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \ \Sigma} נתון.
  • המילה הריקה: מילה שאורכה 0, נהוג לסמן את מילה זו על ידי הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \ \varepsilon} .
  • שפה פורמלית: קבוצת מילים פורמליות.

פעולות על מילים

  • אורך של מילה: האורך של מילה שווה למס' האותיות שבה. אורכה של מילה הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \ w} מסומן בהפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \ |w|} .
  • מס' מופעי אות במילה: מס' מופעי הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \ \sigma} במילה הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \ w} יסומן בהפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \ \#_{\sigma}(w)} .
  • היפוך מילים: תהי הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \ w={\sigma}_{1}{\sigma}_{2}...{\sigma}_{n}} . היפוכה יסומן ב ויתקיים הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \ w^{R}={\sigma}_{n}{\sigma}_{n-1}...{\sigma}_{1}} .
  • שרשור מילים: יהיו שתי מילים הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \ w,z} כך שהפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \ w={w}_{1}{w}_{2}...{w}_{n} , z={z}_{1}{z}_{2}...{z}_{n}} שרשורן יסומן על ידי או הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \ wz} ויוגדר כ-הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \ {w}_{1}{w}_{2}...{w}_{n}{z}_{1}{z}_{2}...{z}_{n}} .
  • חזקה של מילה: הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \ w^{n}} מוגדרת רקורסיבית כשרשור של הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \ w} לעצמה הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \ n} פעמים -הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle w^n = \begin{cases} \varepsilon , & n=0 \\ w^{n-1}w, & n>0 \end{cases}} .

פעולות על שפות

  • איחוד/חיתוך/השלמה: פעולות אלו זהות לפעולות איחוד חיתוך והשלמה מתורת הקבוצות, רק שאלו פועלות על שפות (כאשר העולם הוא הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \ \Sigma^{*}} ).
  • שרשור שפות: שרשור של שתי שפות מוגדר כקבוצת כל המילים הנוצרות משרשור מילה אחת מהשפה הראשונה ומילה אחת מהשנייה. כלומר, יהיו הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \ L_{1}, L_{2}} שפות, שרשורן יסומן ב-הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \ L_{1}L_{2}} . הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle L_1\cdot L_2 =\{w \cdot v | w \in L_1 \and v \in L_2 \} }
  • חזקה של שפה: החזקה ה-הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \ n} -ית של שפה מוגדרת כשפת כל המילים הנוצרות על ידי שרשור של הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \ n} מילים מאותה שפה. כלומר, תהי הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \ L} שפה פורמלית. חזקתה תוגדר כך - הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \ L^{0}=\{\varepsilon\}} ולכל הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \ n>0} יתקיים הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \ L^{n}=LL^{n-1}} . הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle L^n = \begin{cases} \{ \varepsilon \}, & n=0 \\ L^{n-1}L, & n>0 \end{cases}}
  • סגור קלין: סגור קלין של שפה הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \ L} יסומן בהפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \ L^{*}} ויוגדר כך - הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \ L^{*}=\bigcup_{i\ge 0}^{\infty } L^{i}} .
  • סגור חיובי: הסגור החיובי של שפה מוגדר בדומה לסגור קלין שלה - הסגור החיובי מסומן בהפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \ L^{+}} ומוגדר כך - הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \ L^{+}=\bigcup_{i>0}^{\infty } L^{i}} .

ההיררכיה של חומסקי

ההיררכיה של חומסקי מחלקת את השפות הפורמליות ל-4 סוגים לפי הדקדוקים היוצרים אותן (כל אחד מהדקדוקים בהיררכיה מוגבל יותר מאלו שמעליו):

דרכים להצגת שפה פורמלית

  • דקדוק פורמלי: אוסף של משתנים דקדוקיים, סימנים טרמינליים וכללי שכתוב המשמשים להגדרת שפה פורמלית.
  • מכונות:
    • אוטומט סופי: המכונה המוגבלת ביותר, משמשת להגדרת שפות רגולריות. לאוטומט זה קבוצה סופית של מצבים המשמשים לו כזיכרון. (מוגבל)
    • אוטומט מחסנית: אוטומט בעל זיכרון לא מוגבל, אבל הגישה אליו מוגבלת. (כפי שניתן להסיק משמו, זיכרון אוטומט המחסנית פועל כמחסנית, שניתן לקרוא רק את הנתון הנמצא בראשה) אוטומט זה מקבל מילים באמצעות ריקון המחסנית או באמצעות הגעה למצב מקבל.
  • ביטוי רגולרי: שיטה להצגת שפות רגולריות באמצעות מספר סופי של פעולות איחוד, שרשור וסגור.

משפטים

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