forked from CS234319/safot
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathtrees.tex
142 lines (129 loc) · 6.72 KB
/
trees.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
§ חתימות וביטויים פורמליים
אנו רואים באיור שמספר הבנים של צומת המכיל את האות~$a$ אינו קבוע. בחלק
מהעצים לצומת זה אין בנים כלל, ואילו בעצים אחרים יש לצומת זה בן אחד, שני
בנים, ואף שלושה. כדי להגדיר עצים שבהם לכל צומת מסוג מסויים יש תמיד מספר
בנים, נזדקק למושג החתימה.
\החל{definition}[חתימה] חתימה~$Γ$, הינה אלפאבית, (בדרך כלל סופי) עליו מוגדרת
פונקצית ערכיות~$\arity$ המתאימה לכל אות~$γ∈Γ$ מספר שלם אי שלילי,~$\arity:Σ→ℕ⁺$.
עבור חתימה~$Γ$, נסמן ב-$Γₙ$ את תת הקבוצה של איברי~$Γ$
שה-$\arity$ שלהם הוא~$n$
\begin{equation*}
Γₙ=❴γ∈Γ\,|\,\arity(γ)=n❵.
\end{equation*}
\סוף{definition}
ביטויים פורמליים מעל חתימה דומים לעצים מעל אלפאבית, בצירוף המגבלה שלצומת
המסומנת באות~$n_γ∈Γ$, יש בדיוק~$\arity(γ)$ בנים. פורמלית,
\החל{definition}[ביטויים פורמליים מעל חתימה]
בהנתן חתימה~$Γ$ אזי,~$E(Γ)$, קבוצת הביטויים הפורמליים מעל~$Γ$
מוגדרת באמצעות הבנאי ה-$n$ מקומי,
\begin{equation*}
\infer{γ(τ₁,⋯,τₙ)∈T(Γ)}{γ∈Γ & n≥0 &γ∈Γₙ&τ₁∈T(Γ) &⋯&τₙ∈T(Γ) }
\end{equation*}
\סוף{definition}
\פסקה{דוגמה: ביטויים סימבוליים כביטויים פורמליים}
בהינתן אלפאבית~$Σ$, נבנה ממנו חתימה~$Γ$ באופן הבא:
\begin{align*}
& Γ=Γ₀∪Γ₂ ⏎
& Γ₀=Σ ⏎
& Γ₂=❴⌘.❵
\end{align*}
קל לראות שהביטויים הפורמליים ב-$E(Γ)$ הם בדיוק בעלי אותו מבנה כמו הביטויים
הסימבוליים בקבוצה~$S(Σ)$.
\פסקה{דוגמה: ביטויים חשבוניים}
נסתכל למשל על החתימה הבאה
\begin{equation}
\begin{split}
& Γ=Γ₀∪Γ₁∪Γ₂ ⏎
& Γ₀=❰⌘0,⌘1,⌘2,⌘3,⌘4,⌘5,⌘6,⌘7,⌘8,⌘9❱^*⏎
&\quad=❴⌘0,⌘1,⌘2,…,⌘10,⌘11,…,⌘{100},⌘{101},…,⌘{1000},⌘{1001},…❵ ⏎
& Γ₁=❴⌘-,⌘!❵ ⏎
& Γ₂=❴⌘+,⌘*,⌘/❵
\end{split}
\end{equation}
גדלה של חתימה זו הוא אינסופי. ה-arity של הסימנים~$⌘+$,~$⌘*$ ו-$⌘/$
הוא 2, ה-arity של הסימנים ⌘! ו-$⌘-$ הוא 1, וה-arity של קבוצת המספרים
הטבעיים הוא 0. קבוצת הביטויים מעל חתימה זו היא לא אחרת מאשר קבוצת הביטויים
החשבוניים הבנויים ממספרים הטבעיים, האופרטורים הבינאריים של חיבור, כפל וחילוק,
והאופטורים האונאריים של השלילה, העצרת, והוצאת השורש. כמה ביטויים בקבוצה זו
מודגמים באיור הבא:
\begin{figure}[!ht]
\centering
\begin{tikzpicture}[every node/.style={shape=circle,
draw, align=center,
top color=red!10, bottom color=blue!20}]
\begin{scope}[yshift=-10ex,start chain=growing right,minimum size=2em]
\node[on chain,circle,draw]{⌘1};
\node[on chain,circle,draw]{⌘0};
\node[on chain,circle,draw]{⌘!} child {node {⌘3}};
\node[on chain,circle,draw]{⌘!} child {node{⌘*} child{node{⌘a}} child{node{⌘-} child{node{42}}}};
% \node[on chain,circle,draw,xshift=5ex]{⌘√{}}
child {node{⌘/}
child {node{5}}
child {node{3}}
}
;
\end{scope}
\end{tikzpicture}
\כיתוב|ביטויים חשבוניים כעצים מעל חתימה|
\end{figure}
נשים לב שההגדרה במובן זה שהיא קובעת את מבנה העצים, ולא את המשמעות שלהם. אין שום
דבר בהגדרה הנותן משמעות של חיבור לסימן ה-⌘+. ההגדרה גם אינה מעניקה משמעות
לקבוצת המספרים הטבעיים. לדידה של ההגדרה, מספר טבעי הוא סדרת ספרות
נטולת משמעות.
§ ביטויים רגולריים
ביטויים רגולריים הם מכשיר חשוב להגדרת שפות פורמליות מעל אלפאבית נתון. ביטויים
רגולריים דומים במבנה שלהם לביטויים חשבוניים: הם עצים, אשר בצמתים פנימיים נמצא
אופרטורים בעלי arity ידוע, כאשר בעלים נמצאים סימנים מתוך האלפאבית.
§§ ביטויים רגולריים כביטויים מעל חתימה
בהינתן אלפאבית~$Σ$, נבנה מעליו חתימה~$Γ$, כאשר~$Γ=Γ₀∪Γ₁∪Γ₂$ וכן
\begin{equation*}
\begin{split}
Γ₀ &=Σ^* ⏎
Γ₁ &=❴⌘*❵ ⏎
Γ₂ &=❴⌘;,⌘|❵
\end{split}
\end{equation*}
נגדיר כעת את~$\RE(Σ)$ קבוצת הביטויים הרגולריים מעל האלפאבית~$Σ$ כקבוצת
הביטויים מעל החתימה~$Γ$,
\begin{equation*}
\RE(Σ)=E(Γ)
\end{equation*}
עלים של ביטויים אלו הם מילים מהאלפאבית~$Σ$ ובכלל אלו המילה הריקה~$ε$.
לצמתים פנימיים המסומנים ב-⌘* יש בן אחד בדיוק. לצמתים פנימיים המסומנים ב-⌘;
או ב-⌘| יש שני בנים בדיוק.
\פנה|figure:regexp| מראה כמה ביטויים רגולריים הנבנים כביטויים מעל
האלפאבית~$❴⌘a,⌘b,⌘c❵$
\begin{figure}
\centering
\begin{tikzpicture}[every node/.style={shape=circle,
draw, align=center,
top color=red!10, bottom color=blue!20}]
\usetikzlibrary{trees,chains}
\begin{scope}[start chain=growing right,minimum size=2em]
\node[on chain,circle,draw]{$⌘;$}
child {%
node{$⌘*$}
child{%
node{$⌘|$}
child{node{$⌘a⌘b$}}
child{node{$⌘c$}}
}
}
child{%
node{$⌘*$}
child{node{$⌘b$}}
};
\node[on chain,circle,draw,xshift=8ex]{$⌘*$}
child {%
node{$⌘|$}
child {node{$⌘a$}}
child {node{$⌘|$} child{node{$ε$}} child{node{$⌘c$}}}
}
;
\end{scope}
\end{tikzpicture}
\כיתוב{ביטויים רגולריים כביטויים מעל החתימה~$Γ=Γ₀∪Γ₁∪Γ₂$, הכוללת את
העלים~$Γ₀=❴⌘a, ⌘b, ⌘c❵^*$, האופראטור האונארי~$Γ₁=❴⌘*❵$ ושני האופראטורים
הבינאריים,~$Γ₂=❴⌘;,⌘|❵$}.
\label{figure:regexp}
\end{figure}