www.vustudents.ning.com

We non-commercial site working hard since 2009 to facilitate learning Read More. We can't keep up without your support. Donate.

# 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.

Views: 13814

### 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??

1

2

3

## Latest Activity

3 hours ago
8 hours ago
Hamza( Graphic Designer) and Mehreen Tasneem are now friends
8 hours ago
Minahil khalid left a comment for ☞De Veloper☜♨
11 hours ago
Aijaz khan updated their profile
14 hours ago
Aijaz khan joined + M.Tariq Malik's group

### CS202 Fundamentals of Front End Development

14 hours ago
Ribqa, Muhammad Rizwan Ansari, Muhammad Imran and 3 more joined Virtual University of Pakistan
14 hours ago
14 hours ago