Explore BrainMass
Share

Programming Languages

Automata and Computability

A Boolean formula is a Boolean circuit wherein every gate has only one output wire. The same input variable may appear in multiple places of a Boolean formula. Prove that a language has a polynomial size family of formulas if it is in NC1. Ignore uniformity considerations. See attached file for full problem description.

Proof by contradiction

Show the error in the following fallacious "proof" that P  NP. Proof by contradiction. Assume that P = NP. Then SAT  P. So, of some k, SAT  TIME(nk). Because every language in NP is polynomial time reducible to SAT, NP  TIME(nk). Therefore P  TIME(nk). But, by the time hierarchy the

Testing for Useless States in Pushdown Automata

A useless state in a pushdown automaton is never entered on any input string. Consider the problem of testing whether a pushdown automaton has any useless states. Formulate this problem as a language and show that it is decidable.

Automata and Computability

Show that the collection of decidable languages is closed under the operations of a. union. b. concatenation. c. star. d. complementation. e. intersection

Automata and Computability for Pumping Length

Consider the language B = L (G), where G is the grammar given in Exercise 2.13 (page 121). The pumping lemma for context-free languages, Theorem 2.19 (page 115), states the existence of a pumping length p for B. What is the minimum value of p that works in the pumping lemma? Justify your answer.

Automata and Computability NOPREFIX

Say that string x is a prefix of string y if a string z exists where xz = y and that x is a proper prefix of y if in addition x  y. In each of the following parts we define an operation on a language A. Show that the class of regular languages is closed under that operation. a. NOPREFIX (A) = {w  A| no prope

Normalizing your Data Base to the Third Normal Forum

Normalize to the 3NF the following collections of data attributes, Write the normalized entities in the correct format and underline the attributes which form the primary key(s). Make whatever assumptions that you need to, but document your assumptions. 1) Video Tapes (Title, Director, Actors, Date, Music Tracks, Duration, Th

Coding for Excel

I am trying to write code that would sum 5 cells and then round to either .00, .25, .50, or .75 depending upon what range the sum of the cells falls into. Example if the sum of the cells equals 1.17 then I would need to round to 1.25. If the sum of the cell equals 15.38 I would need it to round to 15.50. So if the range of the d

Super keyword in Java

Read this article from the Sun website: http://paul.rutgers.edu/java_tutorial/java/javaOO/subclass.html Concerning classes and inheritance. Why is the super keyword so important? Present examples of how inheritance can be found in real-life situations

Push down automata

Give the state transitions for a pda with only 2 states, for the language "a^n b^2n", where n >=1 .

Establishing table structure

You are now going to create the final table list for Fernando's Skate Shop. Use the following preliminary field list and list of subjects to get started. Realize that the lists are incomplete and you may need to add more information as necessary by inferring data from what you know about the case. Be sure to provide a rationale

Run Length Encoding of a Bit Sequence

(a) Encode the following bit sequence using run-length encoding with 4-bit codes eighteen zeroes, 11, fifty-six zeroes, 1, fifteen zeroes, 11. (b) Encode the same sequence using run-length encoding with 5-bit codes (c) Compare the two codes. Comment on two choices.

Program test data and fields for library items records

[a] Discuss and suggest a good set of test data for a program that gives an employee a $50.00 bonus cheque if the employee has produced more than 1,000 items in a week. [b] Assume that a library keeps a file with data about its collection, one record for each item the library loans out. Name at least eight(8) fields that mig

What is RSS?

What is RSS? Describe a real-world application that uses RSS.

Data

Mr. Oldie wants to share his wisdom too, but on a different topic: "These OO-guys looked at hardware assembly and car assembly mechanisms and dreamed that they can do it in software. They aimed for the moon using OO paradigm, but they ended up in clouds! OOD/OOP does not really make such "stand-alone" components that fit togethe

Could a function also be called an inheritance?

In computer programming would you say that a function could also be called an inheritance product due to the reuse of it in the program? A while loop that calls the function once the statement is true can be used over and over. What do you think?

Question 2

Why would a programmer intentionally code the following line into a program? #define true 1 while(true) { // Stuff inside loop. }

Coding and programming

Examine this code snippet and explain why it will work or why not it will not. (Code needed to make this a complete program intentionally left out.) char a; for(a = 'a';a < 'm';a++) printf("%cn");

ranges and functions

You have functions that you wish to call for various individual year values, as well as ranges of years, and you are deciding on whether to use an if statement or a switch statement. The ranges and functions are: o 1900 to 1969 - functionA() o 1969 to 2000 - functionB() o 2001 - functionC() o

write-write, read-write, and write-read dependencies

Find the write-write, read-write, and write-read dependencies in the following assembly language program: I1: LOAD R1, A // R1 -MEMORY (A) I2: ADD R2, R1 //R2 -R2 + R1 I3: ADD R3, R4 //R3 -R3 + R4 I4: MULTI R4, R5 //R4- R4 * R5

Object Oriented System Design with UML

? Build use case diagrams and write use case descriptions ? Build class diagrams for static system modeling ? Build collaboration and sequence diagrams for dynamic system modeling Aims This assignment aims to establish a basic familiarity with the object-oriented system design and the use of UML for system modelling Ob

language generated by the following grammars

Please see attached file for detail (1) Describe the language generated by the following grammars: 1. <expression>  <expression> <woperator> <term> | <term> 2. <term> <id> <soperator> <term> | <id> 3. <id>  a | b| c 4. <woperation>  * 5. <soperator>  + | - (2) 1. <S>  a<A> b | b <B>