Scribd
Upload
137 views

P1 P2

This document provides instructions for constructing deterministic finite automata (DFAs) and non-deterministic finite automata (NFAs) to recognize various formal languages. It includes 25 examples of languages to build DFAs for, ranging from languages based on counts of symbols to patterns contained within strings. It also provides 16 examples of languages to build NFAs for, including some that use epsilon transitions or have bounded numbers of states. Students are to use JFLAP software to complete the automata constructions.

Uploaded by

compiler&automata
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOC, PDF, TXT or read online on Scribd
137 views

P1 P2

This document provides instructions for constructing deterministic finite automata (DFAs) and non-deterministic finite automata (NFAs) to recognize various formal languages. It includes 25 examples of languages to build DFAs for, ranging from languages based on counts of symbols to patterns contained within strings. It also provides 16 examples of languages to build NFAs for, including some that use epsilon transitions or have bounded numbers of states. Students are to use JFLAP software to complete the automata constructions.

Uploaded by

compiler&automata
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOC, PDF, TXT or read online on Scribd
You are on page 1/ 2

ALIGARH COLLEGE OF ENGINEERING & TECHNOLOGY, ALIGARH

B.TECH. CSE/IT SECOND YEAR (2018-2019)


(THEORY OF AUTOMATA & FORMAL LANGUAGES LAB (RCS-453))
(USE JFLAP SOFTWARE ONLY)

(P1) Construct Deterministic Finite Automata (DFA) for the Following:


(1)L={w| na(w) mod 3=2 & nb(w) mod 2=1}.
(2)L={ w| na(w) mod 3>= nb(w) mod 2}.
(3)L=(a*+b*).
(4)L={w | w (starts with a & even #a’s) or ( starts with b & odd # a’s)}.
(5)L={w | w contains at least 1a’s & 1 b’s }.
(6)L={w | w having first and last symbols same, wƐ{a,b}*} .
(7)L={(01)i 12j | i>=1, j>=1}.
(8)L={ an bm | n is divisible by 2 and m is divisible by 4}.
(9)L={w | string w either starting with 01 or ending with 01}.
(10) L={ w| every run of a’s has either two or three}.
(11)L={w | |na(w) -nb(w)| mod 3>0}.
(12)L={the set of all strings such that every block of three consecutive symbols contains at least two zeros}.
(13)Design a DFA which accepts the set of strings over alphabets,∑={1,2,3,4} such that string when
interpreted as decimal numbers , sum of their digits are divisible by 5.
(14)Design a DFA that reads strings made up of letters C, H, A, R, M and recognizes those strings that
containing the word ‘RAM’ as a substring.
(15)Design a DFA which can accept a ternary number divisible by 4.
(16)L={an bn |n<5}.
(17) All Strings containing CAT or RAT as a substring where ∑={C,H,A.R,O,T}.
(18)Design a DFA for a language, L={w | w ε{a,b,c}*and w contains the pattern abac}.
(19)L={w| (na(w) X nb(w) mod 3=1}.
(20)L={w | |w| mod 5≠0}.
(21)L={ w | |w| mod 3=0,|w|≠6}.
Note:- A run in a string is a substring of length at least two, as long as possible and consisting entirely
of the same symbol”. For instance, the string abbbaab contains a run of b’s of length three and
a run of a’s of length two.
(22)L ={wε∑={a,b}*| w contains no runs of length less than four}.
(23)L={wε∑*| na(w) is even and nb(w) mod 3=2}.
(24)L={ wε∑*| every 00 followed by 1}.
(25) L={wε∑*| all strings containing 00 but not 000}.

(P2) Construct Non Deterministic Finite Automata (NDFA/NFA) for the Following:
(1)L= (a*+b*).
(2) L={w | w having first and last symbols same, wƐ{a,b}*} .
(3)Using ε-transitions, design NFA for accepting the language, L={(ab)*U aa*}.
(4)L=(aa)*+(aaaa)*.
(5)L={w | w ended with either ab or ba}.
(6)Design a NFA to recognize the following set of strings , 0101,101 and 011. Assume the alphabet is {0,1}.
(7)The set of all strings over {0,1,2,3,….,9}, such that the final digit appears before.
(8)Design NFA no more than 5 states for ,{ababn |n>=0} U{aban |n>=0}.
(9)Design NFA with 3 states that accepts , L={an |n>=1}U {bm ak |m>=0,k>=0}.
(10)Design NFA with out λ-transition for language , L={a}U {bn |n>=1}.
(11)L={an | n>=0}U{bn a|n>=1}.
(12)All strings that contains the substring 0|01(5 states).
(13)(11+11111)*
(14)L=a*b*c*.
(15)L={vwv| v,wƐ{a,b}*, |v|=2}.
(16)L={an | n is either a multiple of three or a multiple 5}.

You might also like