### 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 […]

## Theory of Computation

## 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). […]

## Definition Non Deterministic Finite Automata

A non-deterministic finite automaton (NDFA/NFA) is a 5-tuple (Q, Σ, δ, q0, F) where, Q = is a finite set of states. Σ = is a finite set of input symbols. δ = is a transition function mapping from Q × Σ to 2Q. q0 = is the initial state, q0 ∈ Q. F = is […]

## 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 […]

## CNF from S–>aAD;A->aB/bAB;B->b,D->d.

RGPV 2020 Find the grammar in Chomsky Normal form equivalent to S–>aAD;A->aB/bAB;B->b,D->d. Ans. A context free grammar (CFG) is said to be in chomsky normal form (CNF) if all its productions are of the form- A → BC A → a where A, B, C are non-terminals and a is a terminal. This CFG […]

## NDFA accepting two consecutive a’s or two consecutive b’s.

RGPV 2020Construct a NDFA accepting all string in {a,b} with either two consecutive a’s or two consecutive b’s. Ans.

## Regular expresion to CFG

RGPV 2020 Write given CFG for R.E (011 + 1)*(01)*. Ans. CFG for (011 + 1)* A –> CA A –> ε C –> 011 | a CFG for (01)* B –> DB B –> ε D –> 01 Final CFG for (011 + 1)*(01)* S –> AB A –> CA | ε C –> […]

## Regular expression to Regular grammar

RGPV 2020 How can we construct regular grammar from regular expression? Ans. Lets take an regular expresion example: 0*(1(0+1))* Now convert above example in to regular language. 0*(1(0+1))* Conver above regular expression into Right linear regular grammar in step by step. Step 01: S –> 0S Step 02: S –> 0S | A | ∈ […]

## Grammar is ambiguous. S → aSbS|bSaS|∈

RGPV 2020 Show that the following grammar is ambiguous. S → aSbS|bSaS|∈ Ans. For grammar to be ambiguous, there should be more than one parse tree for same string. Above grammar can be written as S → aSbS S → bSaS S → ∈ Lets generate a string ‘abab’. So, now parse tree for ‘abab’. […]

## leftmost and rightmost derivations

RGPV 2020 What are leftmost and rightmost derivations? Explain with suitable example ? Grammar: S → aS / ∈ For generating strings ‘aaa’. Left most derivation: A leftmost derivation is obtained by applying production to the leftmost variable in each step. S → aS → aaS (Using S → aS) → aaaS […]

## Construct Moore machine for Mealy machine

RGPV 2020Construct Moore machine for the following Mealy machine. Sol. Transition table for above Mealy machine. Present State Next State Input = 0 Input = 1 State Output State Output q0 q0 0 q1 1 q1 q2 2 q0 0 q2 q1 1 q2 2 Transition table for Moore machine from above Mealy machine transition […]

## CFL are not closed under intersection

RGPV 2020 Preve that CFL are not closed under intersection ? If L1 and If L2 are two context free languages, their intersection L1 ∩ L2 need not be context free. For example, L1 = { anbncm | n >= 0 and m >= 0 } L1 says number of a’s should be equal to number […]

## NFA to DFA | RGPV TOC

RGPV 2009 Q. Construct minimized DFA for the given NFA. Or Convert the following NFA into DFA. Ans. Transition table for given NFA State Input a B è q0 q0, q1 q0 q1 q2 q1 q2 q3 q3 q3 – q2 Transition table for DFA from given NFA table State Input a B è [q0] […]

## Moore to Mealy | RGPV TOC PYQ

RGPV 2009Construct a Mealy mcahine which is equivalent to the Moore mchine given below. Present State Next State Output a = 0 a = 1 q0 q1 q2 1 q1 q3 q2 0 q2 q2 q1 1 q3 q0 q3 1 Ans. Mealy machine Present State Next State a = 0 a = 1 Next […]

## DFA accept even 0 and even 1 |RGPV TOC PYQ

RGPV 2011Design FA which accepts even no. of 0’s and even no. of 1’s.Or RGPV 2010Construct DFA ove input alphabet Σ = {0,1} to accept string which contains no. of 0 is even and no. of 1 is even.Or RGPV 2008Construct DFA accepting set of all strings containing even no. of a’s and even no. of […]

## 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 […]

## DFA ending with 00 start with 0 no epsilon | RGPV TOC PYQ

RGPV 2015Q. Design DFA accepting the following languages over the alphabet {0, 1} The set of all words ending in 00. The set of all words except ε. The set of all words that begin with 0. Ans. 1. The set of all words ending with 00: Some example strings = {00, 100, 000, 1000,0100,11100} Regular […]

## DFA ending with 101 | RGPV TOC PYQ

RGPV 2006Q. Give DFA accepting the language over alphabet {0,1} such that all strings of 0 and 1 ending in 101. Ans. Some example strings = {101, 10101, 01101, 00101, 111o1, 1101} Regular expression = (0+1)*101 Minimum number of states required = 4

## Construct DFA for a power n, n>=0 || RGPV TOC

RGPV 2009Q. Construct DFA for anb | n>=0. Ans. Some example strings = {ab, aab, aaab, aaaab} Minimum number of states required = 2.

## Construct FA divisible by 3 | RGPV TOC PYQ

RGPV 2010Construct a finite automta that will accept those strings of a binary number that are divisible ny three.or RGPV 2009construct DFA for binary integer divisible by 3 Ans. Some example strings = {0, 11, 110, 1001, 1100} Minimum number of states required = 4

## Construct DFA equivalent to NFA | RGPV TOC PYQ

RGPV 2014Q. Construct DFA equivalent to the NFAM = ({p, q, r, s}, {0, 1}, δ, p, {q, s})Where δ is defined in the following table. δ 0 1 p {q, s} {q} q {r} {q, r} r {s} {p} s – {p} Ans. State 0 1 [p] [q, s] [q] [q] [r] [q, r] [q, s] […]