Finite State Machines (FSMs) ka Taaruf

Finite State Machines (FSMs) ka Taaruf

• Finite State Machines (FSMs) ko Finite Automata bhi kaha jata hai.
• Finite Automata ko do badi categories mein taqseem kiya jata hai:
  • Finite Automata with Output
  • Finite Automata without Output

Finite Automata with Output

• Is category mein do types hain:
  • Murri Machine
  • Mealy Machine

Finite Automata without Output

• Is category mein teen types hain:
  • Deterministic Finite Automata (DFA)
  • Nondeterministic Finite Automata (NFA)
  • Epsilon Nondeterministic Finite Automata (Epsilon NFA)
• Is dars mein, tawajjah Deterministic Finite Automata (DFA) par markooz ki jayegi.

Finite State Machines ki Aham Khususiyat

• Finite State Machines, computation ka sab se aasaan model hai.
• Finite State Machines ki memory mehdood hoti hai.

Deterministic Finite Automata (DFA)

• DFA ka pura naam Deterministic Finite Automata hai.
• DFA ki saakht ko wazeh karne ke liye aik diagram istemal hota hai.
• Diagram mein circles States (halatein) ko zahir karte hain, jinke naam A, B, C, aur D hain.
• Edges (arrow) Transitions (tabdeeliyon) ko zahir karte hain.
• Edges par labeling Inputs (dakhlay) hoti hain, jaise 0 aur 1.
• Transition ka matlab hai ke kis input par state (halat) tabdeel hoti hai.
• State A mein agar input 1 milta hai, to state A se B mein chale jayenge.
• Isi tarah, state A mein input 0 milta hai, to state A se C mein chale jayenge.
• State A par aik arrow hai jo kahin se nahi aa raha, is ka matlab hai ke yeh DFA ki starting state ya initial state hai.
• State D mein do circles hain, is ka matlab hai ke yeh final state ya terminating state hai.

DFA ki Rasmi Tareef (Formal Definition)

• Har DFA ko panch (5) tupules (Q, Σ, q0, F, δ) ke zariye define kiya ja sakta hai.
  • Q States ke set (majmooa) ko zahir karta hai.
  • Σ Inputs (dakhlay) ko zahir karta hai.
  • q0 Starting state (ibtidayi halat) ko zahir karta hai.
  • F Final states ke set (majmooa) ko zahir karta hai.
  • δ Transition function (tabdeeli ka amal) hai jo Q x Σ se Q tak map karta hai.
• Misal ke taur par, DFA ke liye values is tarah hain:
  • Q = {A, B, C, D}
  • Σ = {0, 1}
  • q0 = A
  • F = {D}
• Transition function (δ) ko table ke zariye zahir kiya ja sakta hai, jis mein har state aur input ke liye next state (agli halat) batai jati hai.

Transition Table ki Misaal

• State A mein agar input 0 milta hai, to hum state C mein chale jayenge.
• State A mein agar input 1 milta hai, to hum state B mein chale jayenge.
• Isi tarah, har state aur input ke liye next state table mein batai jati hai.

Khulasa

• DFA ki bunyadi saakht mein states, inputs, starting state, final states, aur transition function shamil hain.
• Transition function batata hai ke har state mein kis input par state tabdeel hoti hai.
• Mazeed wazahat ke liye aane wale lectures mein aur misalen di jayengi.

Finite State Machines (FSMs) computation ka sab se aasaan model hai aur is ki memory mehdood hoti hai. Finite Automata ki taqseem do badi categories mein ki jati hai: Finite Automata with Output aur Finite Automata without Output. Is lecture mein hum Deterministic Finite Automata (DFA) par tawajjah markooz karen ge.