Questions and Answers of SQL Database Programming

(i) Suppose that L is a finite language whose words are w1 , w2 , w3 , • • • , w83 . Prove that there is a TG that accepts exactly the language L.(ii) Of all TGs that accept exactly the
Given a TG, called TG1 , that accepts the language L1 and a TG, called TG2, that accepts the language L2, show how to build a new TG (called TG3) that accepts exactly the language L1 + L2.
Given a TG for some arbitrary language L, what language would it accept if every + state were to be connected back to every - state by Λ-edges? For example, by this method,
(i) Let the language L be accepted by the transition graph T and let L not contain the word Λ. Show how to build a new TG that accepts exactly all the words in L and the word Λ.(ii) Given TG1 that
An FA with four states was sitting unguarded one night when vandals came and stole an edge labeled a. What resulted was a TG that accepted exactly the language b* . In the morning the FA was
Let the language L be accepted by the transition graph T and let L not contain the word ba. We want to build a new TG that accepts exactly L and the word ba.(i) One suggestion is to draw an edge from
Let L be any language. Let us define the transpose of L to be the language of exactly those words that are the words in L spelled backward. If w El, then reverse(w) El. For example, ifL = {a abb
Transition graph T accepts language L. Show that if L has a word of odd length, then T has an edge with a label with an odd number of letters.
A student walks into a classroom and sees on the blackboard a diagram of a TG with two states that accepts only the word Λ. The student reverses the direction of exactly one edge, leaving all other
Let us now consider an algorithm for determining whether a specific TG that has no Λ-edges accepts a given word:Step 1 Number each edge in the TG in any order with the integers 1, 2, 3, . . . , x,
Each of the following is a Moore machine with alphabet Σ = {a b} and output alphabet Γ = {0 1} . Given the transition and output tables, draw the machines.(i)(ii)(iii)(iv)(v) a 90 91 91
Give recursive definitions for the following languages over the alphabet {a b}:(i) The language EVENSTRING of all words of even length.(ii) The language ODDSTRING of all words of odd length.(iii) The
(i) Consider the following recursive definition of 3-PERMUTATION:Rule 1 123 is a 3-PERMUTATION.Rule 2 If xyz is a 3-PERMUTATION, then so are zyx and yzx.Show that there are six different
(i) Let us reconsider the regular expression(a + b)*a(a + b)*b(a + b)*Show that this is equivalent to(a + b)*ab(a + b)*In the sense that they define the
Describe (in English phrases) the languages associated with the following regular expressions:(i)
(i) Explain why we can take any pair of equivalent regular expressions and replace the letter a in both with any regular expression R and the letter b with any regular expression S and the resulting
Consider all the possible FAs over the alphabet {a b} that have exactly two states. An FA must have a designated start state, but there are four possible ways to place the + 's:Each FA needs four
Show that there are exactly 5832 different finite automata with three states. x, y, z over the alphabet {a b}, where x is always the start state.
Suppose a particular FA, called FIN, has the property that it had only one final state that was not the start state. During the night, vandals come and switch the + sign with the - sign and reverse
We define a removable state as a state such that if we erase the state itself and the edges that come out of it, what results is a perfectly good-looking FA.(i) Give an example of an FA that contains
Build an FA such that when the labels a and b are swapped the new machine is different from the old one but equivalent (the language defined by these machines is the same).
Describe in English the languages accepted by the following FAs:(i)(ii)(iii)(iv) Write regular expressions for the languages accepted by these three machines. a, b a a, b
The following is an FA over the alphabet Σ = {a b c}. Prove that it accepts all strings that have an odd number of occurrences of the substring abc. b, c 6+ a b a 2 b b 5+ a a b 3 C 4 + b. c
Consider the following FA:(i) Show that any input string with more than three letters is not accepted by this FA.(ii) Show that the only words accepted are a, aab, and bab.(iii) Show that by changing
Let us consider the possibility of an infinite automaton that starts with this infinite binary tree:Let L be any infinite language of strings of a's and h's whatsoever. Show that by the judicious
Consider the language S*, where S = {ab ba}. Write out all the words in S* that have seven or fewer letters. Can any word in this language contain the substrings aaa or bbb? What is the smallest word
Consider the language S*, where S = {a ab ba} . Is the string (abbba) a word in this language? Write out all the words in this language with six or fewer letters. What is another way in which to
Consider the language S*, where S = {aa aba baa} . Show that the words aabaa, baaabaaa, and baaaaababaaaa are all in this language. Can any word in this language be interpreted as a string of
Consider the language S*, where S = {xx xxx}. In how many ways can x19 be written as the product of words in S? This means: How many different factorizations are there of x19 into xx and xxx?
Consider the language PALINDROME over the alphabet {a b}.(i) Prove that if x is in PALINDROME, then so is xn for any n.(ii) Prove that if y3 is in PALINDROME, then so is y.(iii) Prove that if zn is
Show that if the concatenation of two words (neither A) in PALIN DROME is also a word in PALINDROME, then both words are powers of some other word; that is, if x and y and xy are al l in PALINDROME,
Prove that for all sets S,(i) (S+)* = (S*)*(ii) (S+)+ = S+(iii) Is (S*)+ = (S+)* for all sets S?
Suppose that for some language L we can always concatenate two words in L and get another word in L if and only if the words are not the same. That is, for any words w1 and w2 in L where w1 ≠ w2,
Let w be a string o f letters and let the language T be defined as adding w to the language S. Suppose further that T* = S*.(i) Is it necessarily true that w ∈ S?(ii) Is it necessarily true that w
One student suggested the following algorithm to test a string of a's and b's to see if it is a word in S*. where S = {aa ba aba abaab}. Step 1, cross off the longest set of characters from the front
A language L1 is smaller than another language L2 if L1 ⊂ L2 and L1 ≠ L2• Let T be any language closed under concatenation; that is, if t1 ∈ T and t2 ∈ T. then t1 t2 is also an element of
Using the second recursive definition of the set EVEN, how many different ways can we prove that 14 is in EVEN?
Using the second recursive definition of EVEN, what is the smallest number of steps required to prove that 100 is EVEN? Describe a good method for showing that 2n is in EVEN.
Show that the following is another recursive definition of the set EVEN :Rule 1 2 and 4 are in EVEN.Rule 2 If x is in EVEN, then so is x + 4.
Using any recursive definition of the set EVEN, show that all the numbers in it end in the digits 0, 2, 4, 6, or 8.
The set POLYNOMIAL defined in this chapter contains only the polynomials in the one variable x. Write a recursive definition for the set of all polynomials in the two variables x and y.
Are there any substrings of length 3 that cannot occur that do not contain forbidden substrings of length 2? (This means that /// is already known to be illegal because it contains the forbidden
The rules given earlier for the set AE allow for the peculiar expressions (((((9))))) and - ( - ( - ( - (9)))) It is not really harmful to allow these in AE, but is there some
(i) When asked to give a recursive definition for the language PA LINDROM E over the alphabet Σ = {a b}, a student wrote:Rule 1 a and b are in PALINDROME.Rule 2 If x is in PALINDROME, then so are

Showing 200 - 300 of 244

1
2
3