Mark: 1 revision(s)

2008-03-08T22:35:28Z

1 revision(s)

← Older revision	Revision as of 22:35, 8 March 2008
(No difference)

Mark at 22:58, 6 October 2006

2006-10-06T22:58:05Z

New page

'''1. Let S be a k letter alphabet. Prove that for any given n, the number of strings over this alphabet of length n is equal to k^n.'''

For an alphabet of size 1, the number of ways a string of length n can be written is on. e.g. if the alphabet consists of 'a' the number of 6 letter strings which can be made from this is 1, "aaaaaa". For a two letter alphabet, again with the example of 6, there are 2x2x2x2x2x2 or 64 different possible combinations. For an alphabet with size k alphabet, the number of 6 letter strings is kxkxkxkxkxk or k^6. As such it is clear that changing 6 to 7 would give the number of 7 letter strings. The equation for any number length is thus k^n.

'''2. On the set �⋆ consider the following relations:'''
*'''(a) SubString = {(w, u) | w is a substring of u}.'''
*'''(b) Prefix = {(w, u) | w is a prefix of u}'''
'''Prove that SubString relation is reflexive and transitive. Prove that Prefix relation is reflexive, transitive and antisymmetric.'''

'''3. Let U, V and W be languages. Prove the following equality: U · (V ·W) = (U · V ) ·W.'''

*Let U = {aa}
*Let V = {bb)
*Let W = {aba}

By taking a string accepted by each language and concatenating in the from U · (V ·W) -> aa · (bbaba) -> aabbaba. This string is accepted by all three languages. (U · V ) ·W -> (aabb) · aba -> aabbaba, wich is the same as U · (V ·W).

'''4. Prove that U⋆∪V ⋆ ⊆ (U ∪V )⋆.Write down conditions of languages U and W that guarantee the equality U⋆ ∪ V ⋆ = (U ∪ V )⋆.'''

'''5. Let M be a DFA. Prove that the run of M on any given string w is unique.'''

'''6. Draw transition diagrams of DFA that recognize the following languages. The alphabet is always {a, b}.'''
*'''(a) {w1 | w ∈ �⋆}.'''
*'''(b) {�}.''''
*'''(c) {w | w ∈ �⋆ and w 6= �}.'''
*'''(d) {uaabv | u, v ∈ �⋆}.'''

'''7. Construct the union and intersection automata for the following languages:'''
*'''(a) {uabv | u, v ∈ �⋆} and {ubbv | u, v ∈ �⋆}.'''
*'''(b) {u | the length of u equals 0 modulo 3} and {u | u contains even number of a}.'''

'''8. Prove that every finite language is DFA recognizable.'''

'''9. LetM1 andM2 be DFA recognizing languages L1 and L2, respectively. Give a formal proof that the DFA M1 ⊕M2, M1 ⊗M2, and M(c) 1 recognize the languages L1 ∪ L2, L1 ∩ L2, and �⋆ \ L2, respectively.'''

'''10. Draw transition diagrams for DFA recognizing the union and intersection of the languages {w | w ∈ {ab}⋆ and w w contains an odd number of a’s and an even number of b’s} and {aw | w ∈ {a, b}⋆}.'''

'''11. Let A be a DFA. Consider the DFA B obtained by removing all the states in A that are not reachiable from the initial state of A. Prove that A and B are equivalent.'''

'''12. Let A = (S, q0, T, F) and B = (S′, q0; , T ′, F′) be equivalent minimal DFA. Prove that there exists a function f : S → S′ that satisfies the following properties:'''
*'''(a) The function f is a bijection.'''
*'''(b) For any state s and symbol � ∈ �, f(T (s, �)) = T ′(f(s), �).'''
'''Comment: This exercise shows the equivalent minimal automata A and B are the same since one can be relabeled to get the other.'''

211L12Solutions - Revision history

Mark: 1 revision(s)

Mark at 22:58, 6 October 2006