4 of 9 Search document
Problem-01:
Draw a DFA for the language accepting strings starting with ‘ab’ over input alphabets ∑ =
{a, b}
Solution-
Regular expression for the given language = ab(a + b)*
Step-01:
All strings of the language starts with substring “ab”.
So, length of substring = 2.
Thus, Minimum number of states required in the DFA = 2 + 2 = 4.
Related titles
It suggests that minimized DFA will have 4 states.
Step-02:
We will construct DFA for the following strings-
ab
aba
abab
Step-03:
The required DFA is-
Problem-02:
Draw a DFA for the language accepting strings starting with ‘a’ over input alphabets ∑ = {a,
b}
Solution-
Regular expression for the given language = a(a + b)*
Step-01:
All strings of the language starts with substring “a”.
So, length of substring = 1.
Thus, Minimum number of states required in the DFA = 1 + 2 = 3.
It suggests that minimized DFA will have 3 states.
Unlock this document Upload to download
Upload a document to download this document
or subscribe to read and download. Start your 30 day free trial
Step-02: OR
Unlock this page a er an ad 5
We will construct DFA for the following strings-
a
aa
Step-03:
The required DFA is-
Problem-03:
Draw a DFA for the language accepting strings starting with ‘101’ over input alphabets ∑ =
{0, 1}
Solution-
Regular expression for the given language = 101(0 + 1)*
Step-01:
All strings of the language starts with substring “101”.
So, length of substring = 3.
Thus, Minimum number of states required in the DFA = 3 + 2 = 5.
It suggests that minimized DFA will have 5 states.
Step-02:
We will construct DFA for the following strings-
101
1011
10110
101101
Step-03:
The required DFA is-
Problem-04:
Draw a DFA that accepts a language L over input alphabets ∑ = {0, 1} such that L is the set
of all strings starting with ’00’.
Solution-
Regular expression for the given language = 00(0 + 1)*
Step-01:
All strings of the language starts with substring “00”.
So, length of substring = 2.
Thus, Minimum number of states required in the DFA = 2 + 2 = 4.
It suggests that minimized DFA will have 4 states.
Step-02:
We will construct DFA for the following strings-
00
000
00000
Step-03:
The required DFA is-
Problem-05:
Construct a DFA that accepts a language L over input alphabets ∑ = {a, b} such that L is
the set of all strings starting with ‘aa’ or ‘bb’.
Solution-
Regular expression for the given language = (aa + bb)(a + b)*
Step-01:
Minimum number of states required in the DFA = 5.
It suggests that minimized DFA will have 5 states.
Step-02:
We will construct DFA for the following strings-
aa
aaa
aaaa
bb
bbb
bbbb
Step-03:
The required DFA is-
Problem-06:
Construct a DFA that accepts a language L over input alphabets ∑ = {a, b} such that L is
the set of all strings starting with ‘aba’.
Solution-
Regular expression for the given language = aba(a + b)*
Step-01:
All strings of the language starts with substring “aba”.
So, length of substring = 3.
Thus, Minimum number of states required in the DFA = 3 + 2 = 5.
It suggests that minimized DFA will have 5 states.
Step-02:
We will construct DFA for the following strings-
aba
abaa
abaab
abaaba
Step-03:
The required DFA is-
Reward Your Curiosity
Everything you want to read.
Anytime. Anywhere. Any device.
Read free for 30 days
No Commitment. Cancel anytime.
Share this document
You might also like
Document 12 pages
DFA Solved Examples
Laiba Babar
100% (5)
Document 7 pages
Binary File Questions
Namita Sahu
No ratings yet
Document 10 pages
Answer:: Convert The Following To Clausal Form
5140 - SANTHOSH.K
No ratings yet
Document 23 pages
DFA and NFA Complete Examples
Abbas Hasan
100% (1)
Document 6 pages
Practice Questions of CPP - Multiple Inheritance
Shubham Kumar
100% (2)
Document 34 pages
A Practical File of Data Structure Lab BCA-206: Session: 2020-21
Gaurav Mehndiratta
100% (1)
Document 23 pages
Engineering Mathematics-III Important University Questions Unit-I Fourier Series Two Marks
veludeepa
100% (10)
Document 18 pages
C Programing Unit 4 Notes
Praveena Gopi
100% (4)
Document 10 pages
Nfa To Dfa C Code
Maz Har Ul
100% (1)
Document 10 pages
DFA Diagrams
sam4ets
No ratings yet
Document 27 pages
Closure Properties of Regular Languages
shruti
No ratings yet
Document 22 pages
Loops in C
Dr-Samson Chepuri
No ratings yet
Show more
About Support Legal Social Get our free apps
About Scribd Help / FAQ Terms Instagram
Everand: Ebooks & Audiobooks Accessibility Privacy Twitter
SlideShare Purchase help Copyright Facebook
Press AdChoices Cookie Preferences Pinterest
Join our team! Do not sell or share my personal
information
Contact us
Invite friends
Documents
Language: English Copyright © 2024 Scribd Inc.
