Formal logic and discrete mathematics for computer sci
£20-250 GBP
In Progress
Posted over 8 years ago
£20-250 GBP
Paid on delivery
6 Problems to solve within 5-10 hours.
Please bid asap and we will have a chat to discuss the math problems further.
Purpose
To improve your understanding of finite-state automata, and regular and context-free languages.
To develop design and analysis skills. To use formal tools in reasoning about complex concepts.
To practice the eloquent expression of a precise, formal, argument.
Six problems
Question 1
In the context of the alphabet Σ = {0, 1}, consider the languages A = (0∪1)
∗
0(0∪1)
Construct a minimal DFA that recognizes A \ B, that is, the set of strings that are in A but not
in B. Show your workings, so that it is clear how you have arrived at the resulting DFA. Finally
give a regular expression for A \ B.
Question 2
Give a regular expression for the language generated by the context-free grammar ({S, T}, {a, b}, R, S)
with this set R of rules:
Question 3
S → a S a | a T | b
T → a T | b T | ǫ
For each of the following languages, each over the alphabet {a, b}, determine whether it is regular
or not. Justify your answer in each case.
a. A is the set of strings w such that the number of as in w, and the number of bs in w, are
both multiples of 3. In other words, if w has m occurrences of a and n occurrences of b then
m and n are (possibly different) multiples of 3.
b. B = {a
3i
b
3j
| i, j ≥ 0}.
c. C = {a
Question 4
3i
b
3i
| i ≥ 0}.
Let F be an arbitrary finite language and let R be an arbitrary regular language.
a. Show that if language L is not context-free then L \ F is not context-free either.
b. Show that if language L is not context-free then L ∪ F is not context-free either.
c. Prove or disprove this: If language L is not context-free then L\ R is not context-free either.
d. Prove or disprove this: If language L is not context-free then L∪R is not context-free either.
Question 5
For two languages A and B, define A♦B = {xy | x ∈ A and y ∈ B and |x| = |y|}. Here |w| denotes
the length of the string w. Show that if A and B are regular, then A♦B is context-free.
∗
and B = 0
∗
.
Question 6
Consider the unification algorithm presented in Lecture 8. In each step a set of term equations is
rewritten into a slightly different set. The algorithm as presented is locally non-deterministic. In
each rewriting step, several “equation transformations” (given by rules 1 to 6 on slide 8-8) may be
applicable. In Lecture 13 we came back to this rewriting system as an example of an algorithm
for which termination is not obvious. We noted that, in each rewriting step almost anything can
grow: the number of equations, the number of variable occurrences, the number of function symbols
(including constants) that appear in the equations, the depth of terms, etc. The second rewriting
step on slide 13-21 also shows that, even if we focus on the occurrences of function symbols on the
left-hand sides of the equations, still that number may grow.
Many algorithms are given in this form, as a sequence of non-deterministic state transformations,
starting from an initial state. In our case, a state is a set of term equations. The usual tool for
proving termination of such an algorithm is to define some “measure” on the state and show that
this measure gets strictly smaller in each rewrite step. If the measure is, say, a natural number,
then the strategy clearly works, because the initial state must have some measure n ∈ N, and we
can only decrease a natural number a finite number of times.
As argued above, it is not clear what such a measure would be in our case. So it is not at
all obvious that the unification algorithm always terminates. Your task is to show that it does.
Assume that the “failure rules” (rules 2 and 5) get applied as soon as an opportunity arises.
Hint: Use well-foundedness of a well-chosen lexicographic ordering.
Hi, I am a Computer Science major with highest grade in the courses "Syntax & Semantics" and "Advanced Semantics". I can send you my graduation papers if needed.
I can solve your 6 problems, but within your time frame, I will spend a big part of my night sleep during that and be totally wasted at work tomorrow (the time is almost midnight in Denmark), so my bid will be 111£ (100£ to me), and I will need half the payment up front, and the rest incrementally as each exercise is delivered.
Hello Sir...
My price is negotiable.
I am a computer science teacher, I teach (among others) Automata and Algorithms.
I have done many projects like this, please check my profile.
Please contact me for more details when possible.
I look forward to work for you Sir.
Best Regards.
£100 GBP in 0 day
5.0 (42 reviews)
5.3
5.3
5 freelancers are bidding on average £132 GBP for this job
Hi , I am computer science graduate in my final year of top college with CPI of 8.8 and I had my course of formal logic and automata theory and year ago. I can answer all your problems