Category: TOC

Remove ∈ transitions from NFA

Sol. Step 01: Find ∈-closure of (q1), (q2) and (q3).∈-closure of (q1) = {q1, q2, q3}∈-closure of (q2) = {q2, q3}∈-closure of (q3) = {q3} For each state find the next state for each input. See the table below, State 0 1 2 ->q1 {q1,q2,q3} {q2,q3} {q3} q2 φ {q2,q3} {q3} q3 φ φ {q3} […]

Pushdown Automata

A Pushdown automata (PDA) works similar as DFA. A DFA can remember a finite amount of information, but a PDA can remember an infinite amount of information. A PDA can be formally described as a 7-tuple (Q, ∑, S, δ, q0, I, F) − Q: Finite number of states ∑: Input alphabet S: Stack δ: […]

Diiference between Mealy and Moore machine

Mealy machine has 6 tuples: (Q, q0, ∑, O, δ, λ’) Q : Finite set of states In diagram below Q = {A,B,C,D} q0 : Initial state/ Starting state In diagram below A is initial state ∑ : Input alphabet In diagram below input alphabets are {0,1} O : Output alphabet In diagram below output […]

Moore to Mealy machine

Convert the following Moore machine to Mealy machine. In Moore machine, each input symbol, have the pair of next state and the output.For q0 output is 1, for q1 output is 0, for q2 output is 1, for q3 output is1. So corresponding Mealy machine is as follows,

Mealy to Moore Machine

Mealy Machine to Moore Machine Conversion For an input string of length ‘n’, Transition table for Mealy machine. In the transition table, Q0 is associated with output 1 Q1 is associated with output 0 and 1So, let’s Q10 associated with output 0, and Q11 associated with output 1. Q2 is associated with output 0 and […]

Properties of transition functions

RGPV 2015 PYQQ. State and explain the properties of transition functions ? Ans. A transition function is defined on every state for every input symbol. Transition Function (δ) is defined as δ = Q X Σ –> Q. Where, Q is set of all states. Σ is set of input symbols. Properties of transition functions: […]

Equivalent of DFA and NFA

RGPV 2010, 02Q. Write short note on equivalent of DFA and NDFA ? Ans.Every DFA is an NDFA.If from a regular set an NDFA is created than there may be chances of existence of DFA.DFA is 5 tuple machine:M = (Q, Σ, δ, q0, F) Q is a finite non empty set of states. Σ […]

Minimization of DFA

Construct a minimum state automata equivalent to given automata ? (RGPV 2008) Solution: Transition table for above automata. State Input = a Input = b ->q0 Initial state q1 q3 q1 q2 q4 q2 q1 q1 q3 q2 q4 q4 Final state q4 q4 Step 01: Remove steps which are unreachable from initial states. Step […]

Construct NFA without ∈

Construct NFA without ∈ transitions NFA with ∈ Sol. Step 01: Find ∈-closure of (q1), (q2) and (q3). ∈-closure of (q1) = {q1, q2, q3}  ∈-closure of (q2) = {q2, q3} ∈-closure of (q3) = {q3} For each state find the next state for each input. See the table below, State 0 1 2 ->q1 […]

NFA with ∈ to DFA Indirect Method

Indirect Method: In this method, Step 01: Convert NFA with ∈ moves to NFA without ∈ moves. Step 02: Than NFA without ∈ moves is converted to the DFA. For example: Convert he following NFA with ε in to DFA using Indirect method of comversion ? Solution: Step 01: Convert NFA with ∈ moves to NFA without ∈ […]

NFA with ∈-Moves

NFA with ∈ moves is exactly same as NFA without ∈ moves. But differece exist in the transition function δ. δ must include information about ∈ transitions. NFA with ∈-Moves has 6 tuples (Q, Σ, δ, q0, F).Where, Q = finite set of states. Σ = finite set input symbols.δ = transition function that maps Q × (Σ ∪{∈}) to 2Q.q0 […]

Arden’s Law

Arden’s law is used in simplification of regular expression. It is states as, for p, q and r to be regular expressions, and if ∈ is not member of L(P) then the equation in r as r = q + rp has a unique solution given by r = qp* Let us proof that r = […]

Regular expression

A regular expression is a sequence of pattern that defines a string. The language accepted by finite automata can be easily described by simple expressions called Regular Expressions. Operators of regular expression The definition of regular expression includes three basic operators:  Union Concatenation Closure 1. Union: If p and q are regular expressions, then p+q […]

Regular Expression Examples

Example 1: Let Σ = {a, b}. Write regular expression to define language consisting of strings w such that, w contains only a’s or only b’s of length zero or more. Solution:  r = a* + b* Example 2: Let Σ = {a, b}. Write regular expression to define language consisting of strings w such that, w […]

Mealy Machine

In the Mealy machine, the output symbol at a given time is a function of the present input as well as the present state of the machine.  Therefore the transition graph of the Mealy machine cannot be further simplified. Mealy machine is defined as a 6 tuple (Q, Σ, ∆, δ, λ, q0)  where,  Q […]

Moore machine

In this type of machine, the future state Sj of the machine is decided by the current state and current input symbol of the machine.  The output symbol at a given time depends only on the present state of the machine. Moore machine is defined as a 6 tuple (Q, Σ, ∆, δ, λ, q0).  […]

DFA solved examples

Example 1: Draw a DFA for the language accepting strings ending with ‘0’ over input alphabets ∑={0, 1} ?  Solution: Example 2: Draw a DFA for the language accepting strings ending with ‘01’ over input alphabets ∑={0, 1} ? Solution:  Example 3: Draw a DFA for the language accepting strings ending with ‘00’ over input […]

How do a DFA Process Strings?

The important thing about DFA is to know that it identifies the acceptance of strings.  The language of the DFA is the set of all strings that the DFA accepts.  Assume that S1, S2, S3, ….. Sn is a sequence of input symbols.  q0 is the starting states of DFA.  Then first we shall check […]

Notations for DFA

Transition Diagram:  This is a graph in which vertices represent state of machine and the edges show transition of states. The labels on these edges indicate input/output for the corresponding transition.  A transition diagram for a DFA M = (Q, Σ, δ, q0, F) is a graph defined as follows: For each state in Q […]

Definition of Deterministic Finite Automata

A Deterministic Finite Automaton (DFA) consists of a finite set of states and a set of transitions from one state to another state on input symbols selected from an alphabet S.  The initial state is generally denoted by q0.  For each input symbol there is one transition for each state.  There are one or more […]

Short note on automata | RGPV TOC PYQ

RGPV 2010Q. Write short note on automata ? Ans. An automaton is an abstract model of a digital computer.  Some types of automata : Finite-state machine. Pushdown automata. Turing machine A finite automaton (FA) is a simple idealized machine used to recognize patterns within input taken from some character set (or alphabet) C. The job […]