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

### Category: RGPV TOC PYQ

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

## DFA end with 1 contain 00 | RGPV TOC draw

RGPV 2007 Q. Define deterministic finite automta. Draw DFA that accepts any string which ends with 1 or it ends with an even number of 0’s following the last 1. Alphabets are {0,1}. Ans. Some example strings = {1, 001, 01001, 011}

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

## RGPV TOC design finite automata problems

RGPV 2008Prob 01: Designa FA which accepts set of strings containing four 1’s in every string over alphabet ∑ = {0, 1}. Ans. Some example strings = {1111,0110101, 001100110} RGPV 2016Prob 02. Design NFA that accepts all strings with at most 3 a’s. Ans. Some example strings = {aaa, baba, a, ab} RGPV 2014 Prob 03: Construct […]

## RGPV Define Mealy and Moore Machine

RGPV 2010Q. Formally define the following (with example)- Mealy machine Moore machine 1. Mealy machine: Mealy machine is a six tuple machine. M = (Q, Σ, △, δ, λ, q0) Q is finite set of states. Σ is the input alphabet. △ is the output alphabet. δ is transition function which maps Q×∑ → Q. ‘λ’ is the output function which […]

## RGPV TOC Short note on 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 […]

## RGPV notes Write short note on NDFA

RGPV 2002Q. Write a short note on non-deterministic finite automta ? Ans. Non deterministic finite automata refere as NDFA or NFA allows a set of possible moves. For example from a state an input ‘1’ can transit 0 times, 1 times or more than 1 times. Its not determined in NFA like in DFA. NDFA […]

## RGPV TOC What do you understand by DFA how to represent it

RGPV 2015,14,02,03Q. What do you understand by DFA (Deterministic Finite Automata) and how is it represented ? Ans. A DFA means Deterministic finite automata or a finite state automata or a deterministic finite state machine (DFSM) or deterministic finite acceptor (DFA). It is a 5 tuple machine, M = (Q, Σ, δ, q0, F) Q is […]

## RGPV short note on automata

RGPV 2010Q. Write short note on automaton? Ans. An automaton is an abstract self-propelled computing device which follows a predetermined sequence of operations automatically. There are four major families of automaton : Finite-state machine. Pushdown automata. Linear-bounded automata. Turing machine. 1. Finite-state machine: A system where particular inputs cause particular changes in state can be represented […]

## RGPV TOC 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: Property 1: […]

## RGPV TOC What is Trap state

RGPV PYQ 2010 Q. What is trap state in FA ? Ans. If a transition leads to a state from which it can never escape. such a state is called a trap state. For example: In DFA below, state C is a trap state. From C no input is going to another state. […]