اتوماتای برنامه‌نویسی

برنامه‌نویسی مبتنی بر اتوماتیک
اتوماتای بر اساس برنامه‌نویسی نمونه‌ای از برنامه‌نویسی می‌باشد که برنامه و قسمت‌های مختلف آن سعی بر این دارند تا یک ماشین متناهی را مدل کنند.
برنامه‌نویسی مبتنی بر FSM
برنامه نویسی مبتنی بر FSM نیز مانند برنامه‌نویسی مبتنی بر اتوماتیک می‌باشد با این تفاوت که تمامی جنبه‌های ماشین متناهی را پوشش نمی‌دهد.
مشخصه‌های برنامه‌نویسی مبتنی بر اتوماتیک
موارد زیر مشخصه‌های برنامه‌نویسی مبتنی بر اتوماتیک است:
۱-زمان اجرای برنامه به وضوح از مراحل اتوماتا جدا می‌باشد.
۲-ارتباط میان مراحل فقط از طریق رفتن از یک وضعیت به وضعیت دیگر می‌باشد.
تمام مراحل اجرای یک اتومات به‌طور کلی یک چرخه اتوماتا را می‌گویند.
مثال
برنامه‌ای در زبان C را در نظر که یک متن را از ورودی می‌خواند، خط به خط کلمه اول هر خط را چاپ می‌کند.
روش سنتی برنامه‌نویسی C
برنامه زیر می‌تواند مورد بالا را به روش سنتی برنامه‌نویسی C انجام بدهد:
include
int main(void)
int c;
do {
c = getchar();
while(c == )
c = getchar();
while(c != EOF -- c != -- c != \n) {
putchar(c);
c = getchar();
putchar(\n);
while(c != EOF -- c != \n)
c = getchar();
while(c != EOF);
return 0;
روش برنامه‌نویسی مبتنی بر اتوماتیک
همان کاری که برنامه قبل انجام میداد را میتوانیم با ماشین متناهی انجام دهیم.توجه داشته باشید که تجزیه خطوط سه مرحله دارد :
1- عبور کردن از space‌ها
2- چاپ کردن کلمه
3- گذر از همه حروف کلمه
برنامه به شکل زیر می‌باشد :
#include
int main(void)
enum states {
before, inside, after
state;
int c;
state = before;
while((c = getchar()) != EOF) {
switch(state) {
case before:
if(c == \n) {
putchar(\n);
else
if(c != ) {
putchar(c);
state = inside;
break;
case inside:
switch(c) {
case : state = after; break;
case \n:
putchar(\n);
state = before;
break;
default: putchar(c);
break;
case after:
if(c == \n) {
putchar(\n);
state = before;
return 0;
اگرچه برنامه طولانی به نظر میرسد اما مزیت آن این است که فقط یک دستور خواندن دارد و همچنین تنها یک حلقه در برنامه وجود دارد نه 4 عدد.
کاملا لازم نیست کد را به گرداننده‌ها ی جدا برای‌ها وضعیت تقسیم کنیم.برنامه‌ی زیر همان کار برنامه‌ی بالا را انجام می‌دهد با این تفاوت که یک مقدار کوتاه‌تر است.
#include
int main(void)
enum states {
before, inside, after
state;
int c;
state = before;
while((c = getchar()) != EOF) {
if(c == \n) {
putchar(\n);
state = before;
else
switch(state) {
case before:
if(c != ) {
putchar(c);
state = inside;
break;
case inside:
if(c == ) {
state = after;
else {
putchar(c);
break;
case after:
break;
return 0;
تابعی جدا برای مرحله‌ی اتوماتیک
مهمترین ویزگی برنامه قبل این است که کد مرحله اتوماتیک به صورت محلی تعریف شده‌است. با یک تابع جدا برای این قسمت ما بهتر میتوانیم این ویژگی را اثبات کنیم.
include
enum states { before, inside, after ;
void step(enum states *state, int c)
if(c == \n) {
putchar(\n);
*state = before;
else
switch(*state) {
case before:
if(c != ) {
putchar(c);
*state = inside;
break;
case inside:
if(c == ) {
*state = after;
else {
putchar(c);
break;
case after:
break;
int main(void)
int c;
enum states state = before;
while((c = getchar()) != EOF) {
step(-state, c);
return 0;
این مثال به‌طور کامل ویژگی کد مبتنی بر اتوماتا را ثابت میکند.
جدول انتقال صریح و روشن
یک اتوماتای متناهی می‌تواند به‌طور صریح و روشن توسط جدول انتقال بیان شود.
در برنامه زیر جدولی وجود دارد که برای هر ترکیب جدول شامل یک وضعیت جدید و یک پرچم می‌باشد.
include
enum states { before = 0, inside = 1, after = 2 ;
struct branch {
unsigned char new_state:2;
unsigned char should_putchar:1;
struct branch the_table33 = {
/* \n others */
/* before */ { {before,0, {before,1, {inside,1 ,
/* inside */ { {after, 0, {before,1, {inside,1 ,
/* after */ { {after, 0, {before,1, {after, 0
void step(enum states *state, int c)
int idx2 = (c ) ? 0 : (c \n) ? 1 : 2;
struct branch *b = - the_table*stateidx2;
*state = (enum states)(b->new_state);
if(b->should_putchar) putchar(c);
اتوماتا و اتوماسیون
برنامه نویسی مبتنی بر متن نشان دهنده‌ی مطابقت میان برنامه‌نویسی و اتوماسیون می‌باشد.
یک چرخه‌ی تولید به‌طور کلی به صورت زیر مدل می‌شود.
1.مجموعه‌ای از مراحل که با ورودی مطابقت دارد.
2.مجموعه‌ای از کارها که با حالت کنونی مطابقت دارد.
برنامه‌ی نمونه
برنامه‌ای که در بالا ارائه شد از این دیدگاه به صورت زیر بیان می‌شود.
SPC :
EOL : \n
states : (before, inside, after, end)
setState(c) {
if c=EOF then set end
if before and (c!=SPC and c!=EOL) then set inside
if inside and (c=SPC or c=EOL) then set after
if after and c=EOL then set before
doAction(c) {
if inside then write(c)
else if c=EOL then write(c)
cycle {
set before
loop {
c : readCharacter
setState(c)
doAction(c)
until end
اوتوماسیون و رویدادها
در رشته‌ی اوتوماسیون از یک مرحله به مرحله‌ی دیگر رفتن به این بستگی دارد که چه حروفی به دستگاه وارد می‌شود. این می‌تواند این‌گونه ارائه شود که حروف از یک فایل متنی خوانده شود و به ترتیب وارد دستگاه شود. در واقع این اطلاعات در مورد مکان ، سرعت ، دما و دیگر عناصر حیاطی دستگاه می‌باشد.
مانند یک برنامه‌نویسی گرافیکی شاخه‌هایی وجود دارند که با یکدیگر اجرا می‌شوند که به صورت زیر میتوان آن‌ها را نشان داد.
s:stage c:condition
s1
s2
s31 s32
s4
استفاده از ویژگی‌های شی گرا
اگر زبان برنامه‌نویسی از ویژگی‌های شی گرایی استفاده کند میتوان اوتومات‌ها را به صورت یک شی در نظر گرفت. با ابن کار چگونگی پیاده‌سازی آن و جزئیات آن پنهان می‌شود.
به عنوان مثال یک نسخه از برنامه‌ای که در بالا گفته شد با استفاده از ویژگی‌های شی گرایی به صورت زیر نوشته می‌شود.
include
class StateMachine {
enum states { before = 0, inside = 1, after = 2 state;
struct branch {
enum states new_state:2;
int should_putchar:1;
static struct branch the_table33;
public:
StateMachine() : state(before) {
void FeedChar(int c) {
int idx2 = (c ) ? 0 : (c \n) ? 1 : 2;
struct branch *b = - the_tablestateidx2;
state = b->new_state;
if(b->should_putchar) putchar(c);
struct StateMachine::branch StateMachine::the_table33 = {
/* \n others */
/* before */ { {before,0, {before,1, {inside,1 ,
/* inside */ { {after, 0, {before,1, {inside,1 ,
/* after */ { {after, 0, {before,1, {after, 0
int main(void)
int c;
StateMachine machine;
while((c = getchar()) != EOF)
machine.FeedChar(c);
return 0;
کاربردها
اوتوماتای مبتنی بر برنامه‌نویسی به صورت گسترده‌ای در تحلیل لغوی و گرامری استفاده می‌شود.
در نظریه اوتوماتیک فکر نیز می‌تواند مورد استفاده قرار بگیرد.
اوتومات‌های مبتنی بر برنامه‌نویسی برای توصیف معانی بعضی از زبان‌های برنامه‌نویسی مورد استفاده قرار میگیرد.
تاریخجه
تکنیک مبتنی بر اوتومات‌ها به صورت گسترده‌ای در الکوریتم‌ها و نظریه اوتوماتیک استفاده می‌شود. مثل تحلیل زبان‌های با قاعده.
یکی از ابتدایی‌ترین مقاله‌ها در این زمینه در سال 1968 چاپ شد.
اولین جایی که از اوتومات‌های مبتنی در برنامه‌نویسی به عنوان یک تکنیک عمومی نام برده شده‌است در سال 1963 توسط پیتر نور بود که نویسنده آن را تکنیک تورینگ ماشین نام‌گذاری کرده بود.
بیشتر بخوانید
Nondeterministic programming
State pattern
Esterel
Umple