Reference no: EM132730039
CP50004E Theory of Computation - University of West London
Learning outcome 1: Understand the concepts and applications of finite automata
Learning outcome 2: Understand and reason about the concepts of language grammars, and regular expressions in computer programming
Learning outcome 3: Use computational complexity theories such as P, NP and NP-Complete to analyse the efficiency of algorithms
Answer the following questions:
1. Consider the language L of all strings consisting of 0's followed by a (possibly empty) string of 1's followed by a (possibly empty) string of 0's.
a. Draw a deterministic finite automaton that accept this language
b. Formally write down the alphabet of the language
c. Give two strings with the correct alphabet and a minimum length of 7 symbols: one that is accepted and one that is not accepted by this automaton.
d. According to the DFA definition, list the 5-tuple for this automaton.
e. Give a Regular Expression (RE) for L.
2. a. For the language L ⊆ {0,1}*, find a regular expression representing the following:
i. All strings that do not begin with 11
ii. All strings in which every appearance of 0 is followed directly by a 1.
b. Convert the following non-deterministic finite automaton into regular expression:
3. Consider the following CFG with alphabet {a, b} and start variable S: S → AB
A → aAa
B → bBb A → ε
B → ε
a. What is the shortest string in the language of the grammar excluding the empty string?
b. Draw the derivation tree for the string in (a).
c. Explain whether this grammar is ambiguous or not?
d. Describe in English the language generated by the grammar.
e. Explain why this CFG can or cannot generate a regular language.
4. Consider the following non-deterministic PDA:
a. List three strings the PDA accepts.
b. Give the language for this PDA
c. Give CFG for all strings of this language
5. Consider a TM that recognise {w#w : w ∈ Σ }.(Assume the alphabet for w is {a,b})
a. Draw the diagram for a TM that accepts {w#w}
b. Explain how does the above TM works.
6. Consider the following TM with input alphabet {0,1}
a. Is the empty string accepted and why?
b. What is the final string if the input is 01101?
c. Explain exactly what does this TM do to the string on the input tape?
|
Which would increase risk
: Which of the following would increase risk? Decrease the amount of inventory by formulating an effective inventory policy./ Increase the use of fixed cost
|
|
Compute DJ diluted EPS
: There were 100, 000 call options at December 31, 2019, On January 1, Common shares 360,000. Compute DJ diluted EPS for 2019
|
|
What is the effect of increase in a unit contribution margin
: What is the effect of an increase in a unit contribution margin on the product's contribution ratio? No effect on the contribution ratio
|
|
Describe the types of controls
: Describe the types of controls required to ensure the integrity of data entry and processing and uninterrupted eCommerce. Outline the principles of developing.
|
|
CP50004E Theory of Computation Assignment
: CP50004E Theory of Computation Assignment Help and Solution, University of West London - Assessment Writing Service - concepts and applications
|
|
What is the standard time in minutes per unit
: The performance rating was 117%. The worker was idle 20% of the time (so that idle time should be subtracted from the total time
|
|
What impact could a poor quality product have on a company
: What impact could a poor quality product have on a company? How do you think a company can improve their vendor and customer relations
|
|
What is the value of the bullwhip measure for a company
: What is the value of the bullwhip measure for a company with a standard deviation of demand equal to 40, and a variance of orders equal to 450?
|
|
Find the maximum margin linear decision boundary
: Consider the XOR problem where there are four training points: (1, 1, -),(1, 0, +),(0, 1, +),(0, 0, -). Transform the data into the following feature space.
|