We are here with you hands in hands to facilitate your learning & don't appreciate the idea of copying or replicating solutions. Read More>>

www.vustudents.ning.com

 www.bit.ly/vucodes + Link For Assignments, GDBs & Online Quizzes Solution www.bit.ly/papersvu + Link For Past Papers, Solved MCQs, Short Notes & More

Dear Students! Share your Assignments / GDBs / Quizzes files as you receive in your LMS, So it can be discussed/solved timely. Add Discussion

# CS402 Theory of Automata Assignment No 01 Solution & Discussion Due Date: 23-11-2015

CS402 Theory of Automata Assignment No 01 Solution & Discussion Due Date: 23-11-2015

Write regular expressions for the following languages over the alphabet ∑ = {0, 1}:

Question 1;

1. Language of all strings which do not end with 11.
2. Language of all strings which do not contain the substring 01.

Question 2;

Draw Finite Automaton for each of the above described languages.

+ How to Join Subject Study Groups & Get Helping Material?

+ How to become Top Reputation, Angels, Intellectual, Featured Members & Moderators?

+ VU Students Reserves The Right to Delete Your Profile, If?

Views: 12963

.

+ http://bit.ly/vucodes (Link for Assignments, GDBs & Online Quizzes Solution)

+ http://bit.ly/papersvu (Link for Past Papers, Solved MCQs, Short Notes & More)

### Replies to This Discussion

Note for All Members: You don’t need to go any other site for this assignment/GDB/Online Quiz solution, Because All discussed data of our members in this discussion are going from here to other sites. You can judge this at other sites yourself. So don’t waste your precious time with different links.

Complete Solution Guys enjoyyyyyyy ............

Attachments:

can u tell me what is q and e ?

you did not included the diagram

A regular expression for the first one is e + 0 + 1 + S* (00 + 01 + 10) where e is the empty string, S is the alphabet, * is the Kleene closure, + is union. This works because the language can be divided into strings of length less than two (e + 0 + 1) and strings of length at least two which do not end with 11 (this leaves endings 00, 01, and 10).

A regular expression for the second language is 1*0*. Note that we must put any 1s on the left of all 0s to avoid the substring 01, but we can have as many as either as we like.

A DFA for the first one would look like

q    e    q'

q0   0    q0

q0   1    q1

q1   0    q0

q1   1    q2

q2   0    q0

q2   1    q2

State q0 is initial, q0 and q1 are accepting. In state q0, you either just started or last saw a zero; your last symbol wasn't 1. In state q1, your last symbol was 1, but your second to last symbol wasn't. In state q2, you have seen two 1s in a row.

A DFA for the second would look like:

q    e    q'

q0   0    q1

q0   1    q0

q1   0    q1

q1   1    q2

q2   0    q2

q2   1    q2

q0 is the initial state, and q0 and q1 are accepting. q0 reads all the 0s, q1 reads all the 1s, and q2 happens if we see a 0 after we have seen a 1.

Solit@ Doll  thnaks for sharing

Always mention

By the way it's my pleasure

Diagram to khud bna len sub kuch likh to dia hy k kese krna hy her koi pakki pkayi kheer mangta hy khud bhi chamcha hila den na

This is first question solution.

Mohsin Sharif thanks for sharing

is there any mistake in my fa??

## Latest Activity

Rao ! liked +Аүмаи+'s discussion ذرا ذرا سے منافق تو سارے ھوتے ہیں
13 minutes ago
Rao ! liked + ! ! ! ! ! кαнνιѕн꧂'s profile
14 minutes ago
+ ! ! ! ! ! кαнνιѕн꧂ liked +Аүмаи+'s discussion فرمان على
45 minutes ago
45 minutes ago
+ ! ! ! ! ! кαнνιѕн꧂ liked Isha Chuhdary's discussion Trust
45 minutes ago
46 minutes ago
46 minutes ago
+ ! ! ! ! ! кαнνιѕн꧂ liked Rana Ali's discussion Zaroori tha
47 minutes ago
48 minutes ago
48 minutes ago
48 minutes ago
48 minutes ago

1

2

3