Homework 1 Problems
29 sept. 2015 (b) The set of all strings with three consecutive 0's (not ... such that the number of 0's is divisible by five and the number of 1's.
Assignment 1 Due: Oct 17th
such that each block of five consecutive symbols contain at least. {0 (c) The set of strings of 0's and 1's whose number of 0's is divisible by five and.
Automata Theory and Languages
Example: 01101 and 111 are strings from the binary alphabet ? = {01} ?k: the set of strings of length k
Regular Languages [Fa14]
1?(01?01?)? — the set of all binary strings with an even number of 0s. • 0 +1(0 +1)?00 — the set of all non-negative binary numerals divisible by 4 and
B?L 405 Automata Theory and Formal Languages ( B?L 405
c) The set of strings of 0's and l's that do not contain 11 as a substring. d) The set of strings of 0's and l's whose number of 0's is divisible by five.
60-354 Theory of Computation Fall 2011
Construct a DFA that accepts all strings over {01} The set of all strings such that each block of five ... The number of 0's in it.
2.2.1 Some examples of regular expressions
(0 + 1)?: set of all strings over {0 1}. (0 + 1)?001(0 + 1)?: strings 0? + (0?10?10?10?)?: strings with number of 1's divisible by 3. ?0: {}.
Solutions to Problem Set 2
8 févr. 2007 Solution: Any string in the language must be composed of 0 or more blocks each hav- ing exactly five 0's and an arbitrary number of 1's between ...
Homework 2
15 janv. 2015 b) The set of strings of 0's and 1's whose number of 0's is divisible by five. Exercise 2 (Ex 3.1.3 page 92). Write regular expressions for ...
Homework 1
The set of strings of 0's and 1's whose number of 0's is divisible by five. * Exercises above are from Introduction to Automata Theory Languages
Homework 1 Problems - Donald Bren School of Information and
Sep 29 2015 · The set of all strings whose tenth symbol from the left end is a 1 The set of strings that either begin or end (or both) with 01 The set of strings such that the number of 0's is divisible by ve and the number of 1'sis divisible by 3 Exercise 2 2 8 on page 54 of Hopcroft et al
Homework Solutions Proof by contradiction using the - WPI
Pick string = 1p Then we can break string into u v w such that v is not empty and u v < k Suppose v = m Then u w = p – m If the language really is regular the string u vp-m w must be in the language But u vp-m w = p – m+ (p-m)m which can be factored into (m+1)(p-m) Thus this string does not have a length which is prime and
Homework #4 Solutions
#1. Prove that the following is not a regular language: The set of strings of 0's and 1's that are of the form w w Proof by contradiction using the Pumping Lemma The language is clearly infinite, so there exists m (book uses a k) such that if I choose a string with |string| > m, the 3 properties will hold.Pick string = 0
m 10 m1. This has length > m.
So, there is an u, v, w such that string = u v w with |u v| < m, |v| > 0.So uv = 0
n , v = 0 k , and w = 0 m-n 1 0 m 1 And the string u v v w is supposed to also be in the language.But u v v w = 0
n k 1 0 m-n 1 0 m1, and a few minutes staring at this should convince that
there is no way this could be of the form w w (Be sure you see why). #2. Show that the language L = {a p } p is prime is not a regular language Proof by contradiction using the Pumping Lemma The language is clearly infinite, so there exists k such that if I choose a string with |string| > k, the 3 properties will hold.Pick string = 1
p Then we can break string into u v w such that v is not empty and |u v| < k.Suppose |v| = m. Then |u w| = p - m.
If the language really is regular, the string u v
p-m w must be in the language.But, | u v
p-m w| = p - m+ (p-m)m which can be factored into (m+1 )(p-m). Thus this string does not have a length which is prime, and cannot be in L.This is a contradiction.
#3. Suppose h is the homomorphism from {0,1,2} to {a,b} defined by h(0) = a; h(1) = ab; h(2) = ba. a) What is h(21120) h(21120) = ba ab ab ba a b) If L = 01*2, what is h(L)? h(L) = a(ab)*ba c) If L = a(ba)*, what is h -1 (L)?02*U 1*0
#4. a) Show that the question: Does L = *? for regular language L is decidable.First the question Does L =
is decidable: Just have to look at the dfa for L to see if there is a path from the start state to a final state. Now look at the complement of L, L'. It is decidable whether it is empty because the complement of a regular language is regular. If L' is empty, then L =*; otherwise L <> A more interesting proof is that a language is empty (hence its complement is *) if and only if the related dfa accepts a string whose length is less than k, the number of states (Then we have a decision procedure: just check if any strings of length 0, 1, ... k-1 are accepted). You can show this using the pumping lemma! b) Show that the question, Given a FA M over , does M accept a string of length <2? is decidable
This is a finite set: just check each such string to see if if it leads to a final state.quotesdbs_dbs14.pdfusesText_20[PDF] the shape of global higher education volume 4
[PDF] the shapiro test
[PDF] the shelly cashman series collection pdf
[PDF] the smith dc thanksgiving dinner
[PDF] the smith thanksgiving
[PDF] the social meaning of money pdf
[PDF] the solution to the equation is x = .
[PDF] the solvable challenge of air pollution in india
[PDF] the space of love pdf
[PDF] the special theory of relativity pdf
[PDF] the specified image does not contain a windows node and cannot be used for deployment
[PDF] the standard 401k loan application
[PDF] the state of european car sharing
[PDF] the static method cannot hide
