CS 181 Homework Week 2 solution

$24.99

Original Work ?
Category: You will Instantly receive a download link for .ZIP solution file upon Payment

Description

5/5 - (8 votes)

Two: Let La and Lb be the same sets as in the previous homework (as clarified in the Course
Announcements and slightly rephrased for clarity here). Let Σ = { 0, 1 }.
La = All strings over Σ that change from one symbol to the other at most once as you
read the string
Lb = All strings over Σ that begin and end with the same symbol
d. Note that we can also view Σ as a language consisting of just the two strings 0 & 1.
List the elements of the language concatenation:
Σ • (Lb ∩ {strings of length ≤ 2})
e. What is the language concatenation La • {} ?
Six: Consider the two DFAs M1 & M2 (Fig. 1.6 on p. 36 & Fig. 1.8 on p. 37, respectively
of Sipser) and reproduced here for convenience. What is the language
concatenation L(M1) • L (M2) ? I.e., give a simple English description of this
language.
0. Consider the following alternative definition of the transitive closure δ* of the transition function δ
for a DFA:
For a DFA M = (Q, Σ, δ, q0, F), extend δ over symbols in Σ to δ
* over strings in Σ* thusly:
Define δ
*
: ( Q x Σ* ) → Q:
δ
*
( q, ε ) = q , for all q ∈ Q
δ
*
( q, xb ) = δ( δ
*
( q, x ) , b ), for all q ∈ Q, b ∈ Σ, & x ∈ Σ*
a. How would you interpret this version of the definition in English vs. the way we interpreted the
usual definition?
b. Prove this version is equivalent to the usual definition by showing that for any DFA, M, it gives
the same resulting state for all q in Q and input string w in Σ*
. Since they are both recursive
definitions, you’ll want to use induction.
2
1. Let M = ( Q, Σ, δ, q0, F) be a DFA with Σ = {a, b}, Q = {(0,0), (0,1), (1,0), (1,1)}, q0 = (0,0), F = {q0},
and δ given by the formulas:
δ( (x, y), a ) = ( (x+1) MOD 2 , y )
δ( (x, y), b ) = ( x , (y+1) MOD 2 )
where x, y ∈ { 0, 1 }.
a. Give the state transition table for transition function δ.
b. Draw the state diagram for DFA M. (Don’t forget the initial state and final state(s).)
c. Describe in English the language recognized by this DFA.
d. How would you interpret the names of the states in Q in English in terms of how the DFA
works?
Inspired by Sipser Exercises: pp. 83-86:
2. Show a DFA over the alphabet { a, b } for the following language (from Sipser Exercise 1.5.h) via the
complement construction (as in Exercise 1.14.a):
{ w ∈ Σ
*
| w is not the string a nor the string b }
3. Show an NFA over Σ = {0, 1} for the language in Sipser 1.6l:
Lthree = { w ∈ Σ*
| w contains an even number of 0’s or it contains exactly two 1’s}
Can you do it with 6 states?
4. For the following language over Σ = {a, b} (from Sipser Exercise 1.20.h), give two strings which are in
the language and two which are not (total of four strings).
( a ∪ ba ∪ bb ) Σ*
5. Consider the following two languages over Σ = { a, b, c }.
Lfive = { xby | x, y ∈ { a, c }*
and the number of a’s in x = the number of a‘s in y }
LNFS = { an
ban | n ≥ 0 }
As discussed in class, languages like LNFS are not finite state. Prove that Lfive is not finite state using
closure properties of finite state languages and the fact that LNFS is not finite state.
eof