ریاضی را حرف بزن · دانشگاه

عبارت منظم: الگوهای متن

عبارت منظم زبانی کوچک است که یک خانوادهٔ کامل از رشته‌ها را یک‌جا توصیف می‌کند. برنامه‌نویس‌ها هر روز از آن استفاده می‌کنند؛ ریاضی‌دان‌ها می‌پرسند یک الگو کدام رشته‌ها را می‌پذیرد.

پیش‌نویس: نوشتهٔ یک دستیار هوش مصنوعی؛ هنوز معلمی آن را بررسی نکرده است.

الفبا

هر نماد را همان‌طور که زیرش نوشته شده بلند بخوان.

$cat, c.t$ بخوان: c و a و t همان‌طور که نوشته شده‌اند؛ و c نقطه t: نقطه یعنی هر نویسهٔ دلخواهیعنی: حرف‌ها خودشان را نشان می‌دهند؛ نقطه هر یک نویسه را نشان می‌دهد.
$a*, a+, a?$ بخوان: a ستاره: a به هر تعداد، حتی صفر بار؛ a به‌اضافه: دست‌کم یک بار؛ a علامت سؤال: یک بار یا اصلاً نهیعنی: می‌شمارد قطعهٔ قبل از آن چند بار می‌تواند تکرار شود.
$[abc], [a-z], [ˆ a]$ بخوان: کروشه a و b و c: یک نویسه از فهرست؛ a خط‌تیره z: یک نویسه از بازه؛ هَت در ابتدای کروشه: یک نویسه که در فهرست نیستیعنی: یک نویسه که از یک مجموعهٔ مشخص برداشته می‌شود.
$ˆ ab$$ بخوان: هَت، a، b، دلار: رشته از همین‌جا شروع می‌شود، ab است و همین‌جا تمام می‌شودیعنی: الگو را به ابتدا و انتهای رشته می‌چسباند.
$(ab|c)+$ بخوان: داخل پرانتز: ab یا c؛ همهٔ این‌ها یک بار یا بیشتریعنی: خط عمودی بین دو قطعه انتخاب می‌کند؛ پرانتز قطعه‌ها را گروه می‌کند تا یک شمارنده روی همهٔ آن‌ها اثر کند.
$a{2,4}$ بخوان: a، بین دو تا چهار باریعنی: دقیقاً می‌گوید چند تکرار مجاز است: یک عدد یا از و تا.
$\d, \w, \s$ بخوان: بک‌اسلش d: یک رقم؛ بک‌اسلش w: یک حرف یا رقم یا زیرخط؛ بک‌اسلش s: یک فاصلهیعنی: نام‌های کوتاه برای رایج‌ترین ردهٔ نویسه‌ها: رقم‌ها، نویسه‌های واژه و فاصله‌ها.
$s \in L (r) \subseteq Σ^{*}$ بخوان: s عضو L از r است و L از r زیرمجموعهٔ سیگما ستاره استیعنی: L از r مجموعهٔ رشته‌هایی است که r آن‌ها را به‌طور کامل می‌پذیرد؛ سیگما ستاره مجموعهٔ همهٔ رشته‌های روی الفبای Σ است.

داستان: دربان

زیرنویس:

روی هر سطر بزن تا کلمه‌هایش را ببینی.

$r = ˆ [AB]\d$$ قاعدهٔ دربان، r: یک کد یعنی یک حرف A یا B، بعد یک رقم، و دیگر هیچ.
$A7 \in L (r)$ کدی با یک حرف مجاز و یک رقم با قاعده جور است: عضو زبان r است.
$C7 \in / L (r)$ کدی که حرفش C است جور نیست: C در دسته نیست.
$A77 \in / L (r)$ کدی با حرف مجاز و دو رقم برگردانده می‌شود: لنگر پایان می‌گوید کد پس از یک رقم تمام شود.
$r^{'} = ˆ [AB]\d+$$ مراجعه‌کننده‌ها شکایت می‌کنند، پس علامت به‌اضافه یک یا چند رقم را مجاز می‌کند. قاعدهٔ تازه را r′ بنامیم.
$A77 \in L (r^{'})$ حالا همان کد دو رقمی رد می‌شود.
$d = ˆ \d{2}:\d{2}$$ برای ساعت ملاقات، او زمان‌ها را وارسی می‌کند: دو رقم، یک دونقطه، دو رقم. این قاعده را d بنامیم.
$09:30 \in L (d)$ زمانی با دو رقم ساعت رد می‌شود.
$9:30 \in / L (d)$ زمانی با یک رقم ساعت رد نمی‌شود: به‌جای دو رقم، یک رقم دارد.
$L (r) \subseteq L (r^{'}) \subseteq Σ^{*}$ هرچه r بپذیرد r′ هم می‌پذیرد، و هر دو فقط دربارهٔ رشته‌های روی الفبا داوری می‌کنند.

این داستان با کلمه‌ها ۶۷۰ حرف است؛ با نمادها ۹۹.

بخوانش

چه می‌گوید؟

$ˆ ab*$$

$[ˆ 0-9]$

$(ab)+$

$L (r) = Σ^{*}$

$colou?r$

${ˆ}\d{3}-\d{4}$$

$[A-Z][a-z]+$

$\w+\s\w+$

${ˆ}(0|1)*$$

$a.c$

${ˆ}[{ˆ}aeiou]+$$

${ˆ}$$

بنویسش

کدام نمادنویسی همین را می‌گوید؟

یک کد یعنی حرف a یا b یا c و پس از آن دقیقاً سه رقم، و دیگر هیچ.

کل رشته یا cat است یا dog.

رشتهٔ s را الگوی r می‌پذیرد.

کد قفل: دقیقاً دو حرف بزرگ، بعد دقیقاً دو رقم، و دیگر هیچ.

واژهٔ colour که حرف u در آن اختیاری است.

کل رشته جفت ab است که یک بار یا بیشتر تکرار شده.

بین دو تا چهار a، بعد یک b تنها، و دیگر هیچ.

الگوی r هیچ رشته‌ای را نمی‌پذیرد.

رشتهٔ s را الگوی r نمی‌پذیرد.

هر رشته‌ای را که r بپذیرد، r′ هم می‌پذیرد.

یک واژه: یک یا چند حرف یا رقم یا زیرخط، و دیگر هیچ.

کل رشته yes است یا no یا تهی.

بسازش

کاشی‌ها را به ترتیب بزن. یکی از کاشی‌ها اضافه است.

یک زمان از شبانه‌روز: رشته شروع می‌شود، دو رقم، یک دونقطه، رقم دقیقه از ۰ تا ۵، یک رقم دلخواه، رشته تمام می‌شود.

رشتهٔ s را r می‌پذیرد و هر چه r بپذیرد رشته‌ای روی الفباست.

کد صندلی: رشته شروع می‌شود، یک حرف بزرگ از A تا Z، دقیقاً سه رقم، رشته تمام می‌شود.

کل رشته جفت ab یک بار یا بیشتر است و بعد یک c اختیاری.

رشتهٔ s را r می‌پذیرد اما r′ نمی‌پذیرد: s در زبان r منهای زبان r′ است.

برچسب اتاق: رشته شروع می‌شود، یک یا چند حرف کوچک، یک فاصله، یک یا چند رقم، رشته تمام می‌شود.

چالش‌ها

معماهای خلاقانه‌ای که همهٔ نمادهای این فصل را به کار می‌برند. عجله نکن؛ ساعتی در کار نیست.

1 جدول دربان

چهار قاعده (ستون‌ها)، پنج کد (سطرها). s روی پنج کد می‌گردد و r روی چهار قاعده. هر جمله را در این جدول داوری کن.

	$r_{۱} = ˆ [AB]\d$$	$r_{۲} = ˆ [AB]\d+$$	$r_{۳} = ˆ \w\d$$	$r_{۴} = ˆ \d+$$
$A7$	✓	✓	✓
$B12$		✓
$C7$			✓
$77$			✓	✓
$AB$

تیک یعنی کدِ s را قاعدهٔ r به‌طور کامل می‌پذیرد.

$\exists s : s \in L (r_{۱}) \land s \in / L (r_{۲})$
$\exists s : s \in L (r_{۲}) \land s \in / L (r_{۱})$
$\forall s : s \in L (r_{۱}) \Rightarrow s \in L (r_{۳})$
$\forall s : s \in L (r_{۳}) \Rightarrow s \in L (r_{۲})$
$\exists! s : s \in L (r_{۴})$
$\forall s \exists r : s \in L (r)$

2 الگوهای شبیه هم

چهار الگو که فقط در یک کروشه یا ستاره فرق دارند. هر کدام را به چیزی که می‌پذیرد وصل کن (رشتهٔ کامل، ساخته‌شده از a و b).

روی یک سطر بزن، بعد روی معنایش.

3 شمار رقم غلط

این الگو باید سالی با دقیقاً چهار رقم، یک خط‌تیره و ماهی با دو رقم را بپذیرد، مثل «سال چهاررقمی، خط‌تیره، ماه دورقمی» (کل رشته). یکی از کاشی‌ها غلط است. پیدایش کن و درستش کن.

روی کاشیِ غلط بزن.

4 کدام رشته رد می‌شود؟

قاعدهٔ دروازه این است: جفت ab یا یک c، بعد حداکثر یک رقم، و دیگر هیچ. از سه رشته کدام را می‌پذیرد؟

$ˆ (ab|c)\d?$$

5 چند رشته رد می‌شود؟

قاعده فقط رشته‌هایی روی سه حرف a و b و c را می‌پذیرد. زبان این الگو چند رشته دارد؟

$r = ˆ [ab]{3}$, ∣ L (r)∣ = ?$

6 الگویی که همه را راه می‌دهد

زبان الگوی نقطه‌ستاره چیست؟

$L (.*) = ?$

7 وارسی‌گر زمان را بنویس

یک رشتهٔ ساعت از یک ساعت (۰۰ تا ۲۳)، یک دونقطه و یک دقیقه (۰۰ تا ۵۹) ساخته می‌شود، مثل نه و سی دقیقه. الگویی بنویس که دقیقاً همین رشته‌ها را بپذیرد، بعد مقایسه کن.

نوشتهٔ تو

8 با یک مجموعه بگو

زبان الگوی cat|dog را به‌صورت یک مجموعه بنویس.

نوشتهٔ تو

9 پنج پلاک، چهار قاعده

چهار قاعده برای پلاک (ستون‌ها) و پنج پلاک (سطرها). s روی پلاک‌ها می‌گردد و p روی قاعده‌ها. هر جمله را در این جدول داوری کن.

	$p_{۱} = {ˆ}[a-z]+\d*$$	$p_{۲} = {ˆ}[a-z]\d+$$	$p_{۳} = {ˆ}\w+$$	$p_{۴} = {ˆ}(ab\|cd)+$$
$ab$	✓		✓	✓
$ab12$	✓		✓
$a12$	✓	✓	✓
$abcd$	✓		✓	✓
$12ab$			✓

تیک یعنی پلاکِ s را قاعدهٔ p به‌طور کامل می‌پذیرد.

$\forall s : s \in L (p_{۲}) \Rightarrow s \in L (p_{۱})$
$\exists s : s \in L (p_{۴}) \land s \in / L (p_{۱})$
$\exists s : s \in L (p_{۳}) \land s \in / L (p_{۱})$
$\exists! s : s \in L (p_{۲})$
$\forall s \exists p : s \in L (p)$
$\forall s : s \in L (p_{۱}) \Rightarrow s \in L (p_{۴})$

10 قاعده‌های گذرواژه

چهار وارسی برای گذرواژه (ستون‌ها): دست‌کم هشت نویسه؛ فقط نویسهٔ واژه؛ دارای یک رقم؛ فقط حرف کوچک. پنج گذرواژه (سطرها). هر جمله را در این جدول داوری کن.

	$q_{۱} = {ˆ}.{8,}$$	$q_{۲} = {ˆ}\w+$$	$q_{۳} = {ˆ}.\d.$$	$q_{۴} = {ˆ}[a-z]*$$
$hello$		✓		✓
$hello123$	✓	✓	✓
$h3llo_w0rld$	✓	✓	✓
$12345678$	✓	✓	✓
$pass word$	✓

تیک یعنی گذرواژهٔ s از وارسیِ q می‌گذرد.

$\forall s : s \in L (q_{۳}) \Rightarrow s \in L (q_{۱})$
$\forall s : s \in L (q_{۱}) \Rightarrow s \in L (q_{۳})$
$\exists s : s \in L (q_{۴}) \land s \in L (q_{۳})$
$\forall s : s \in L (q_{۴}) \Rightarrow s \in L (q_{۲})$
$\exists! s : s \in / L (q_{۲})$
$\exists s \forall q : s \in L (q)$

11 چند تا a؟

پنج راه برای شمردن حرف a. هر کدام را به چیزی که مجاز می‌کند وصل کن (رشتهٔ کامل).

روی یک سطر بزن، بعد روی معنایش.

12 یک نویسه، کدام؟

پنج الگو برای یک نویسه یا چند نویسه. هر کدام را به چیزی که می‌پذیرد وصل کن.

روی یک سطر بزن، بعد روی معنایش.

13 یک عدد، نه هیچ

این الگو باید رشته‌ای کامل از یک یا چند رقم را بپذیرد. همین‌طور که نوشته شده رشتهٔ تهی را هم می‌پذیرد. یکی از کاشی‌ها غلط است. پیدایش کن و درستش کن.

روی کاشیِ غلط بزن.

14 یک حرف، نه سه حرف

کد یعنی یکی از حرف‌های a یا b یا c، بعد دقیقاً دو رقم، و دیگر هیچ. این الگو هر سه حرف را پشت سر هم می‌خواهد. یکی از کاشی‌ها غلط است. پیدایش کن و درستش کن.

روی کاشیِ غلط بزن.

15 کدام برگردانده می‌شود؟

قاعده هر رشتهٔ کاملی از a و b را می‌پذیرد، حتی تهی. کدام‌یک از سه رشته پذیرفته نمی‌شود؟

$r = {ˆ}[ab]*$, s \in / L (r) : s = ?$

16 چند رشتهٔ دورقمی؟

قاعده رشته‌ای کامل از دقیقاً دو رقم را می‌پذیرد. زبان آن چند رشته دارد؟

$r = {ˆ}\d{2}$, ∣ L (r)∣ = ?$

17 قاعدهٔ پلاک را بنویس

پلاک یعنی دو حرف بزرگ، یک خط‌تیره، بعد سه رقم، و دیگر هیچ. الگو را بنویس، بعد مقایسه کن.

نوشتهٔ تو

18 زوج در دودویی

یک عدد دودویی دقیقاً وقتی زوج است که رقم آخرش ۰ باشد. الگویی بنویس که دقیقاً رشته‌های دودویی عددهای زوج را بپذیرد، بعد مقایسه کن.

نوشتهٔ تو

داستان خودت را بگو

برای یک دروازه (یک گذرواژه، یک پلاک، یک کد در) قاعده‌ای بساز و آن را الگو بنویس؛ بعد یک رشته که می‌پذیرد و یکی که نمی‌پذیرد.

فقط روی همین دستگاه نگه داشته می‌شود.

عبارت منظم: الگوهای متن

الفبا

داستان: دربان

بخوانش

بنویسش

بسازش

چالش‌ها

1 جدول دربان

2 الگوهای شبیه هم

3 شمار رقم غلط

4 کدام رشته رد می‌شود؟

5 چند رشته رد می‌شود؟

6 الگویی که همه را راه می‌دهد

7 وارسی‌گر زمان را بنویس

8 با یک مجموعه بگو

9 پنج پلاک، چهار قاعده

10 قاعده‌های گذرواژه

11 چند تا a؟

12 یک نویسه، کدام؟

13 یک عدد، نه هیچ

14 یک حرف، نه سه حرف

15 کدام برگردانده می‌شود؟

16 چند رشتهٔ دورقمی؟

17 قاعدهٔ پلاک را بنویس

18 زوج در دودویی

داستان خودت را بگو

دانلود برای استفاده بدون اینترنت