PDA

View Full Version : سوال: ماشین متناهی



ordibeheshti
جمعه 29 خرداد 1388, 12:24 عصر
سلام....
من دارم 1ماشین متناهی رو شبیه سازی میکنم.بطوری که مشخصات ماشین رو از ورودی دریافت کنه . شامل

m(Q,S,teta,q0,F
Q{q0,q1,...qn}, S{a,b


سپس یک رشته رو از ورودی بگیره و نهایتا" پاسخ ACCEPT یا REJECT بده.
تا اینجا به این الگوریتم رسیدم که باید با مجموعه حالات و تابع انتقال 1آرایه 2بعدی ساخت و با رشته دریافتی از q0 ,آغاز به پیمایش آرایه کرد و اگر در پایان پیمایش به یکی از حالات نهایی رسید اعلام accept و else اعلان reject کند.
اما در کد نویسیش مشکل دارم...
خیلی ممنون میشم اگرراهنمایی کنید.....

tdkhakpur
جمعه 29 خرداد 1388, 13:49 عصر
سلام
خوب یک مثال دستی بزنید تا بهتر متوجه بشویم.

ordibeheshti
جمعه 29 خرداد 1388, 17:15 عصر
Q{q0,q1,q2حالات ماشین
S{a,b الفبای ماشین
توابع انتقال
teta(q0,a)=q0 //................................... a ................b
teta(q0,b)=q1
teta(q1,a)=q2 //...........................q0......q0 ............q1
teta(q1,b)=q1
teta(q2,a)=q2 //...........................q1..... q2 ...........q1
teta(q2,b)=q2
F=q2 //........................q2.... .q2 ..........q2حالت نهایی
q0=q0 حالت آغازی


حالا مثلا" رشته یدلخواه abaa رو از ورودی گرفتیم.در نتیجه چون به q2 که حالت نهایی میرسیم باید در خروجی accept ببینیم. آرایه ی بالا هم باید خودمون با توجه به مشخصات ماشین تشکیل بدیم . شما نقطه ها رو نادیده بگیرید!!

tdkhakpur
جمعه 29 خرداد 1388, 18:44 عصر
سلام
متوجه مثال شما نشدم شما رشته را متناظر با چی در نظر میگیرید که در نتیجه q2 به حالت نهایی میرسه.
کمی واضحتر توضیح بدید .

ordibeheshti
شنبه 30 خرداد 1388, 10:57 صبح
سلام.......................................... ...
طبق اطلاعات ماشین از نقطه آغاز که q0 است شروع میکنیم و با توجه به حروف رشته دریافتی ,, با توابع انتقال پیش میریم. اولین حرف رشته ورودی a پس ما به سراغ تابع q0,a می ریم که حاصل همون q0 میشه.پس همچنان در q0 هستیم . حرف دوم را میخوانیم , b, پس از تابع q0,b استفاده میکنیم.حاصل q1.
حال در q1 هستیم وحرف بعدیa .پس از تابع q1,a استفاده میکنیم .حاصل q2 .
در q2هستیم حرف بعدی a, تابع q2,a را استفاده میکنیم حاصل q2 و پاپان رشته و حالت نهایی.

pswin.pooya
شنبه 30 خرداد 1388, 13:17 عصر
سلام
من این ماشین رو به کمک قالبها پیاده کردم که توی گیم انجین خودم ازش استفاده میکنم. امیدوارم کدهای زیر به دردت بخوره:


//################################################## ###############
//# title: abstract base class to define an interface for a state
//# file: state.h
//# date: april-26-2009
//# author: Pooya Shahinfar (Pswin)
//################################################## ###############

#ifndef _DENGINE_STATE_H
#define _DENGINE_STATE_H

#include "../../dengine_def.h"
#include "../../core/string.h"

namespace DEngine
{
namespace Game
{
namespace FSM
{
template <class entity_type>
class DENGINE_API State
{
public:
//! Constructor
State(core::string name = L""){};

//! Destructor
~State(){};

//! This will execute when the state is entered
virtual void Enter(entity_type* ent){};

//! Update function of state
virtual void Execute(entity_type* ent)=0;

//! This will execute when the state is exited.
virtual void Exit(entity_type* ent){};

//! Get name of state
core::string GetName(){return m_sName;};

protected:
// name of the state
core::string m_sName;
}; // state
} // FSM
} // Game
} // D-Engine

#endif // _DENGINE_STATE_H

و اما خود ماشین:


//################################################## ###############
//# title: State machine class
//# file: statemachine.h
//# date: april-26-2009
//# author: Pooya Shahinfar (Pswin)
//################################################## ###############

#ifndef _DENGINE_STATEMACHINE_H
#define _DENGINE_STATEMACHINE_H

#include "dengine_def.h"
#include "state.h"

namespace DEngine
{
namespace Game
{
namespace FSM
{
template < class entity_type>
class DENGINE_API StateMachine
{
public:
//! Constructor
StateMachine(entity_type *ent):m_pEntity(ent),
m_pCurrentState(NULL),
m_pGlobalState (NULL),
m_pPreviousState(NULL)
{
};

//! Destructor
~StateMachine();

//! Update
virtual void Update()
{
// if a global state exist then execute it
if(m_pGlobalState) m_pGlobalState->Execute(m_pEntity);

// if a current state exist the execute it
if(m_pCurrentState) m_pCurrentState->Execute(m_pEntity);
}

//! Change to new state
void ChangeState(State<entity_type> *new_state)
{
if (m_pCurrentState)
{
// call exit method of the current state
m_pCurrentState->Exit(m_pEntity);
// change current state with prevous state
m_pPreviousState = m_pCurrentState;
}

// change current state to the new state
m_pCurrentState = new_state;

// call the entry method of the new state
m_pCurrentState->Enter(m_pEntity);
};

//! Change state back to the previous state
void RevertToPreviousState()
{
ChangeState(m_pPreviousState);
}

//! Set Current state
void SetCurrentState(State<entity_type> *_state){m_pCurrentState = _state;};

//! Set Global state
void SetGlobalState(State<entity_type> *_state){m_pGlobalState = _state;};

//! Set previous state
void SetPreviousState(State<entity_type> *_state){m_pPreviousState = _state;};

//! Return a pointer to the current state
State<entity_type> * GetCurrentState(){return m_pCurrentState;};

//! Return a pointer to the previous state
State<entity_type> * GetPreviousState(){return m_pPreviousState;};

//! Return a pointer to the global state
State<entity_type> * GetGlobalState(){return m_pGlobalState;};
private:
//! current state
State<entity_type> *m_pCurrentState;
//! previous state
State<entity_type> *m_pPreviousState;
//! Global state
State<entity_type> *m_pGlobalState;
//! pointer to the entity
entity_type *m_pEntity;
}; // StateMachine
} // FSM
} // Game
} // D-Engine

#endif // _DENGINE_STATEMACHINE_H


برای اینکه یه وضعیت رو تعریف کنی از کلاس state ارث بری کن به عنوان مثال:


calss Walk : public state<person>

توی کد بالا person یه کلاس هستش که یه شخصیت رو تعریف میکنه ( مثلا یک بچه). خوب حالا توی کلاس walk که تعرف کردی باید تابع execute رو بنویسی تا زمانی که ماشین داره پردازش میکنه اون تابع رو اجرا کنه. تابع های exit و Enter هم اختیاری هستن که اگه اونها رو بنویسی به ترتیب، زمان ورود به وضعیت و زمان خروج از وضعیت اجرا میشن.

pswin.pooya
شنبه 30 خرداد 1388, 13:29 عصر
حالات ماشین رو به عنوان وضعیت معرفی کن. بعدش برای (کلاس person که به وضعیتها میدیش) یه تابع update اضافه کن که کاراکتر بعدی از رشته رو برداره. و داخل یه متغییر درونی بذاره و در متد execute کلاس وضعیت اون متغییر رو بخون و تصمیم گیری کن.

پایه هوش مصنوعی بسیاری از بازیهای کامپیوتری مثل the sims همین ماشین وضعیت هستش به عنوان مثال تمام کارکترهای بازی از یک وضعیت (مثل دویدن) به یک وضعیت دیگه ( مثل خوردن) میرن. این وضعیتها در the sims در بالای صفحه نمایش داده میشه.