آج کے تکنیکی دور میں ہارڈ ویئر اور سافٹ ویئر فیلڈ دونوں میں زبردست ترقی دیکھنے میں آئی ہے۔ ہارڈ ویئر ڈیزائن کے طریقوں میں ترقی کے ایک اہم شعبے کو دیکھا گیا۔ کے ساتہ بڑھتی ہوئی ٹیکنالوجی ، ہارڈ ویئر - سوفٹ ویئر کے شریک ڈیزائن کا تصور نافذ کرنا ممکن تھا۔ مختلف طریقوں کو تیار کیا گیا ہے جس کے ذریعہ ، سافٹ ویئر کا استعمال کرتے ہوئے ایک ہارڈویئر سسٹم کو مکمل طور پر ڈیزائن اور انکرن کرسکتا ہے۔ ایسے طریقوں میں سے ایک خودکار تھیوری ہے۔ آٹو میٹا تھیوری کی شاخ ہے کمپیوٹر سائنس جو کمپیوٹنگ ڈیوائسز کے خلاصہ ماڈل کو ڈیزائن کرنے سے متعلق ہے جو خود بخود مرحلوں کے پہلے سے طے شدہ ترتیب کی پیروی کرتا ہے۔ اس مضمون میں آٹو میٹا سبق کے بارے میں مختصر معلومات پر تبادلہ خیال کیا گیا ہے۔
آٹو میٹا تھیوری کیا ہے؟
آٹو میٹا کا لفظ یونانی زبان سے نکلتا ہے ، جس کا مطلب ہے 'خود اداکاری'۔ ایک آٹو میٹن مشین کا ایک ریاضیاتی ماڈل ہے۔ آٹومیٹن ریاستوں اور ٹرانزیشن پر مشتمل ہوتا ہے۔ چونکہ آٹومیٹن کو ان پٹ دیا جاتا ہے یہ منتقلی کے فنکشن کے لحاظ سے اگلی ریاست میں منتقلی کرتا ہے۔ منتقلی کی تقریب کے ل The معلومات موجودہ حالت اور حالیہ علامتیں ہیں۔ اگر کسی آٹومیٹن کی ایک محدود تعداد میں ریاستیں ہوتی ہیں تو ، اسے فائنائٹ آٹو میٹا یا کے نام سے جانا جاتا ہے فائنائٹ اسٹیٹ مشین . محدود آٹوماٹا کی نمائندگی 5-ٹپل (Q، ∑، δ، qo، F) کرتی ہے
کہاں،
Q = ریاستوں کا مکمل سیٹ
ols = علامتوں کا ایک محدود سیٹ ، جسے آٹومیٹا کا حروف تہجی بھی کہا جاتا ہے۔
δ = منتقلی کی تقریب
کیو = ان پٹ کی ابتدائی حالت۔
ایف = کی حتمی ریاستوں کا مجموعہ
آٹو میٹا تھیوری کی بنیادی اصطلاحات
آٹو میٹا تھیوری کی کچھ بنیادی اصطلاحات یہ ہیں۔
1 . الف بے : آٹو میٹا تھیوری میں علامتوں کی کسی بھی حد کو حرف تہجی کے نام سے جانا جاتا ہے۔ حرف کے ذریعہ پیش کردہ - سیٹ {a، b، c، d، e، Al کو الف بے سیٹ کہا جاتا ہے ، جبکہ سیٹ 'a' ، 'b' ، 'c' ، 'd' ، 'e' کو کہتے ہیں علامتیں۔
دو . سٹرنگ : آٹوماٹا میں ، حروف تہجی کے سیٹ سے لی جانے والی علامتوں کا ایک محدود سلسلہ ہوتا ہے example ، مثال کے طور پر ، S = ‘ایڈیڈدادک’ اسٹرنگ حرف تہجی سیٹ∑ = {a، b، c، d، e،} پر درست ہے۔
3 . سٹرنگ کی لمبائی : تار میں موجود علامتوں کی تعداد کو تار کی لمبائی کہا جاتا ہے۔ تار کے ل S S = ‘اڈاڈا’ تار کی لمبائی | S | ہے = 6. اگر تار کی لمبائی 0 ہے ، تو اسے خالی تار کہا جاتا ہے۔
4 . کلین اسٹار : یہ علامتوں on کے سیٹ پر غیر متحرک آپریٹر ہے ، جو سیٹ پر تمام ممکنہ لمبائی λ سمیت all سمیت تمام ممکنہ تار کا لامحدود سیٹ دیتا ہے۔ اس کی نمائندگی مثال کے طور پر ، سیٹ کے لئے Σ = {c، d}، ∑ * = {λ، c، d، cd، dc، cc، dd، ……}۔
5 . کلین بندش : یہ حرف تہجی سیٹ کے ہر ممکنہ تار کا لامحدود سیٹ ہے lud کو چھوڑ کر۔ اس کی طرف سے اشارہ کیا جاتا ہے۔ سیٹ کے لئے Σ = {a، d}، ∑ + = {a، d، ad، da، AA، dd،… ..}۔
6 . زبان : زبان کلینی اسٹار سیٹ - * کچھ الف بے سیٹ سیٹ کے لئے سب سیٹ ہے۔ زبان محدود یا لامحدود ہوسکتی ہے۔ مثال کے طور پر اگر کوئی زبان سیٹ Σ = {a، d over پر لمبائی کے تمام ممکنہ تار لے جاتی ہے ، تو پھر L = {aa ، اشتہار ، دا ، dd}۔
رسمی زبانیں اور آٹو میٹا
آٹو میٹا تھیوری میں ، رسمی زبان ڈور کا ایک سیٹ ہے ، جہاں ہر تار ہوتا ہے علامتوں پر مشتمل محدود حروف تہجی سیٹ set سے تعلق رکھتے ہیں۔ آئیے ایک بلی کی زبان پر غور کریں ، جس میں مندرجہ ذیل لامحدود سیٹ سے کسی بھی تار پر مشتمل ہو…
mew!
meww!
mewww !! ……
بلی کی زبان کے لئے حروف تہجی سیٹ Σ = {m، e، w،! is ہے۔ اس سیٹ کو فائنائٹ اسٹیٹ آٹو میٹا ماڈل-ایم کے لئے استعمال کرنے دیں۔ اس کے بعد ماڈل m کیذریعہ رسمی زبان کی طرف سے اشارہ کیا گیا
ایل (م)
L (m) = {‘mew!’، ‘meww!’، ‘mewww’، ……
آٹومیٹن کسی زبان کی تعریف کے ل useful مفید ہے کیونکہ وہ بند شکل میں لامحدود سیٹ کا اظہار کرسکتا ہے۔ رسمی زبانیں قدرتی زبان جیسی نہیں ہیں جو ہم اپنی روزمرہ کی زندگی میں بولتے ہیں۔ ایک باقاعدہ زبان ہماری باقاعدہ زبانوں کے برعکس ، مشین کی مختلف حالتوں کی نشاندہی کر سکتی ہے۔ رسمی زبان قدرتی زبان جیسے نحو وغیرہ کے کسی حصے کے ماڈل بنانے کے لئے استعمال ہوتی ہے۔ رسمی زبان کی وضاحت محدود ریاست آٹو میٹا سے ہوتی ہے۔ فائنائٹ اسٹیٹ آٹومیٹا کے دو اہم نظریہ ہیں۔ قبول کرنے والے یہ بتاسکتے ہیں کہ کیا تار زبان میں ہے اور دوسرا جنریٹر ہے جو زبان میں صرف ڈور پیدا کرتا ہے۔
ڈیٹرمنسٹک فائنائٹ آٹو میٹا
ڈٹرممینٹک قسم کی آٹو میٹا میں ، جب ایک ان پٹ دیا جاتا ہے ، ہم ہمیشہ طے کر سکتے ہیں کہ منتقلی کس حالت میں ہوگی۔ چونکہ یہ ایک محدود آٹومیٹون ہے ، اس کو ڈیٹرمینسٹک فائنائٹ آٹو میٹا کہا جاتا ہے۔
گرافیکل نمائندگی
اسٹیٹ ڈایاگرام وہ نقشہ ہے جو ڈیٹرمنسٹک فائنائٹ آٹو میٹا کی گرافیکل نمائندگی کے لئے استعمال ہوتا ہے۔ آئیے ایک مثال کے ساتھ سمجھیں۔ عارضی ماہر آٹومیٹا ہونے دو…
Q = {a، b، c، d}۔
Σ = {0 ، 1}
= {a
F = {d اور منتقلی کی تقریب ہو
گرافیکل نمائندگی ٹیبلر فارم
اسٹیٹ ڈایاگرام
ڈیٹرمینسٹک فائنائٹ اسٹیٹ آٹو میٹا کا اسٹیٹ ڈایاگرام
ریاستی آریھ سے
- ریاستوں کی نمائندگی عمودی شکل سے کی جاتی ہے۔
- ٹرانزیشن کی نمائندگی آرک کے ذریعہ ہوتی ہے جس میں ایک ان پٹ حرف تہجی کے ساتھ لیبل لگا ہوتا ہے۔
- خالی واحد آنے والی آرک ابتدائی حالت کی نمائندگی کرتی ہے۔
- دوہری حلقوں والی ریاست حتمی ریاست ہے۔
غیر عزم فاینٹ آٹومیٹا
وہ آٹو میٹا جہاں دیئے گئے ان پٹ کے لئے آؤٹ پٹ حالت کا تعین نہیں کیا جاسکتا ہے اسے نان ڈٹرمینسٹک آٹو میٹا کہا جاتا ہے۔ اس کو غیر متعین عصبی آٹوماتا بھی کہا جاتا ہے ، کیوں کہ اس کی ایک محدود تعداد میں ریاستیں ہیں۔ غیر محافظ Finite Automata کی نمائندگی 5 سیٹ کے سیٹ کے طور پر کی جاتی ہے جہاں (Q، ∑، δ، Qo، F)
سوال = ریاستوں کا محدود سیٹ۔
. = الف بے سیٹ۔
. = منتقلی کی تقریب
کہاں : 
کیو = ابتدائی حالت.
گرافیکل نمائندگی
ریاستی آریگرام کی مدد سے نان ڈٹرمنسٹک فائنائٹ آٹوماٹا کی نمائندگی کی جاتی ہے۔ غیر عزم پر مبنی حد سے پہلے آٹو میٹا ہونے دو
Q = {a، b، c، d
Σ = {0،1}
Qo = {a
F = {d
منتقلی ہیں
گرافیکل نمائندگی ٹیبلر فارم
اسٹیٹ ڈایاگرام
غیر محتاط Finite Automata کا ریاستی ڈایاگرام
آٹو میٹا تھیوری ایپلی کیشنز
کی ایپلی کیشنز خودکار نظریہ مندرجہ ذیل شامل کریں.
- تھیوری آف کمپیٹیشن ، کمپائلر پروڈکشن ، اے ، وغیرہ کے شعبوں میں آٹوماٹا نظریہ بہت مفید ہے۔
- ٹیکسٹ پروسیسنگ کمپیلرز اور ہارڈ ویئر ڈیزائنوں کے ل fin ، محدود آٹو میٹا ایک اہم کردار ادا کرتا ہے۔
- AI اور میں درخواستوں کے لئے پروگرامنگ کی زبانیں ، سیاق و سباق سے پاک گرائمر بہت مفید ہے۔
- حیاتیات کے میدان میں ، سیلولر آٹومیٹا مفید ہے۔
- محدود شعبوں کے نظریہ میں بھی ہم آٹو میٹا کی درخواست پاسکتے ہیں۔
اس مضمون میں ، ہم نے آٹو میٹا تھیوری زبانوں اور حساب کتاب کا مختصر تعارف سیکھا ہے۔ پراگیتہاسک دور سے آٹو میٹا قریب ہی رہا ہے۔ نئی ٹیکنالوجیز کی ایجاد کے ساتھ ہی اس میدان میں بہت ساری نئی پیشرفتیں دیکھنے کو ملتی ہیں۔ آپ کس قسم کا آٹو میٹا لے کر آئے ہیں؟
