Latest Activity In Study Groups

Join Your Study Groups

VU Past Papers, MCQs and More

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


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


Looking For Something? Search Below

Latest Activity

© 2022   Created by + M.Tariq Malik.   Powered by

Promote Us  |  Report an Issue  |  Privacy Policy  |  Terms of Service