[PDF] regular expression to nfa in c
[PDF] regular graph
[PDF] regular language closed under concatenation
[PDF] regular language to regular grammar
[PDF] regular octagonal prism volume
[PDF] regular overtime
[PDF] regular solution
[PDF] regular solution model
[PDF] regular solution model interaction parameter
[PDF] regular solution theory equation
[PDF] regular verb in pdf
[PDF] regular verbs list pdf
[PDF] regularization and optimization
[PDF] regulating body of open and distance education in india
[PDF] regulating body of open and distance learning
CS 330 Formal Methods and Models
Dana Richards, George Mason University, Spring 2017
Quiz Solutions
Quiz 1, Propositional Logic
Date: February 2
1. Prove (((¬p→q)? ¬q)→p) is a tautology
(a) (3pts) by truth table. pq¬p¬q¬p→q(¬p→q)? ¬q(((¬p→q)? ¬q)→p)
TTFFTFT
TFFTTTT
FTTFTFT
FFTTFFT
(b) (4pts) by algebra. (((¬p→q)? ¬q)→p)≡(((¬¬p?q)? ¬q)→p) conditional law ≡(((p?q)? ¬q)→p) law of negation ≡ ¬((p?q)? ¬q)?pconditional law ≡(¬(p?q)? ¬¬q)?pDeMorgan"s law ≡(¬(p?q)?q)?plaw of negation ≡ ¬(p?q)?(q?p) associativity ≡ ¬(p?q)?(p?q) commutativity ≡TRUEexcluded middle 1
2. (3pts) Using onlyp↑q, wherep↑q≡ ¬(p?q), expressp→q.
Note thatp↑q≡ ¬p?¬qby DeMorgan"s law, and for any variableq, (q↑q)≡ ¬(q?q)≡ ¬q. Thus, we have: p→q≡ ¬p?q ≡ ¬p? ¬¬q ≡p↑ ¬q ≡p↑(q↑q) Another equally valid solution isp↑(p↑q). 2
Quiz 2, Rules of InferenceDate: February 9
1. (4pts) Prove ((¬p→q)? ¬q)→p.
1 [(¬p→q)? ¬q] Assumption
2¬p→q?elimination 1
3¬q?elimination 1
4¬¬pModus tollens 2,3
5pDouble negation 4
6 ((¬p→q)? ¬q)→p→introduction 1,5
2. (6pts) Prove (p→q)↔(¬q→p).
1 [p→q] Assumption
2 [¬q] Assumption
3¬pModus tollens 1,2
4¬q→ ¬p→introduction 2,3
5 (p→q)→(¬q→ ¬p)→introduction 1,4
6 [¬q→ ¬p] Assumption
7 [p] Assumption
8 [¬q] Assumption
9¬pModus ponens 6,8
10FALSEContradiction 7,9
11¬¬qReduction to absurdity 8,10
12qDouble negation 11
13p→q→introduction 7,12
14 (¬q→ ¬p)→(p→q)→introduction 6,13
15 (p→q)↔(¬q→ ¬p)↔introduction 5,14
3
Quiz 3, Predicate LogicDate: February 16
1. (6pts) ForA[1...n], assert that every element (i.e. value) occurs ex-
actly twice. "Every element occurs at least twice" ("for every element, there is a different element with the same value"): ?i?In:?j?In:i?=j?A[i] =A[j] "Every element occurs exactly twice" ("every element occurs at least twice, and there are no additional elements with the same value as such a pair"): ?i?In:?j?In:i?=j?A[i] =A[j]?(¬?k?In:k?=i?k?=j?A[k] =A[i])
2. (4pts) Evaluate?x?N:?y?I: (x-y)2-y <0.
False. We may be tempted to choosey=x, resulting in the expression (0)
2-y <0, ory >0. However, this fails whenx=y= 0, which
is part ofN. Indeed, whenx= 0, we are left with (y)2-y <0, or y
2< y, which is impossible to satisfy with integeryvalues.
4
Quiz 4, Mathematical InductionDate: February 23
1. (6pts) Prove
n? i=0x i=xn+1-1 x-1, n≥0, x?= 1.
Whenn= 0, we have
0 i=0x i=x0= 1 =x0+1-1 x-1=x-1x-1= 1
Assume that for somek≥0,
k i=0x i=xk+1-1 x-1, x?= 1
We would like to prove thek+ 1 case,
k+1? i=0x i=x(k+1)+1-1 x-1 To do this, we begin with the left hand side, and substitute the induc- tive hypothesis, k+1? i=0x i=xk+1+k? i=0x i=xk+1+xk+1-1 x-1 (x-1)xk+1 x-1+xk+1-1x-1=x(k+1)+1-xk+1+xk+1-1x-1 x(k+1)+1-1 x-1 This proves the inductive conclusion, thus by mathematicalinduction, the theorem is proved. 5
2. (4pts) Give a formal outline of the proof of?i?I+
k:p(i).
1p(k) Base case
2 [i?I+
k] Assumption
3 [p(i)] Assumption
4p(i+ 1) proof of IC
5p(i)→p(i+ 1)→introduction 3,4
6?i?I+
k:p(i)→p(i+ 1)?introduction 2,5
7?i?I+
k:p(i) Mathematical induction 1,6 6
Quiz 5, Program VerificationDate: March 2
1. (3pts) State, (5pts) prove, and (2pts) apply the loop invariant.
x?4 i?1 whilei < ndo x?6?x i?i+ 1 x?x/3 Proof and application (inference rule version; the application is the whilestep at the very end): Here,Srepresents the code blockx?6?x;i?i+ 1;x?x/3. at the end of the loop,x= 2n+1. 7 Proof and application (inline annotation version; the application is the final comment after the loop): x?4 i?1 whilei < ndo x?6?x i?i+ 1 x?x/3 8 Quiz 6, Mathematical Induction, RevisitedDate: March 9
1. (5pts) Informally prove by induction:n!>3n-1for alln≥5.
Base case,n= 5:
n! = 5! = 120>3n-1= 35-1= 34= 81
Inductive hypothesis,kcase:
Assume thatk!>3k-1for somek≥5
Inductive conclusion,k+ 1 case:
The goal is to prove that (k+ 1)!>3(k+1)-1
Proof:
(k+ 1)! = (k+ 1)k!
By the inductive hypothesis,k!>3k-1, so
(k+ 1)k!>(k+ 1)3k-1
Sincek≥5, it follows thatk+ 1>3, so
(k+ 1)!>(k+ 1)3k-1>3·3k-1= 3k-1+1= 3(k+1)-1 (k+ 1)!>3(k+1)-1 Therefore, by mathematical induction, the statement is proved. 9
2. (5pts)Sn= 2Sn-1+ 1 for alln≥1, andS0= 0.
Prove informallySn= 2n-1 for alln≥0.
Base case,n= 0:
S n=S0= 0 = 2n-1 = 20-1 = 1-1
Inductive hypothesis,k-1 case:
Assume thatSk-1= 2k-1-1 for somek≥1
Inductive conclusion,kcase:
We want to prove thatSk= 2k-1
Proof:
Beginning with the left hand side, and applying the given relationship S n= 2Sn-1+ 1, we getSk= 2Sk-1+ 1
Substituting the inductive hypothesis gives
Sk= 2(2k-1-1) + 1 = 2k-1+1-2 + 1 = 2k-1
S k= 2k-1 Thus, by mathematical induction, the theorem is proved. 10
Quiz 7, Regular ExpressionsDate: March 30
1. (4pts) Give the strings generated of length 5, (ab+a)a?(b+ab).
{abaab,aaaab}. At the beginning of the string, there is a choice ofab ora, and at the end of the string, there is a choice ofborab. Every- thing in between this prefix and suffix must be ana, and the number ofas is fixed by the restriction that the overall length must be 5.Thus, there are 4 possible strings, two of which become reduntant once we notice that, for instance, (a)aaa(b) is the same as (a)aa(ab).
2. (6pts) Give a regular expression for Σ ={a,b},L={x|xdoes not containabb}.
If a string inLcontains anybs, then either thebs must appear isolated from otherbs, or they must appear at the beginning of the string, oth- erwise we would have anabb. If we begin with (a+b)?, the set of all strings, we can modify it by forcing allbs to be preceded by ana, (a+ab)?, which will prevent twobs from appearing in a row. If we also allow for the possibility that the string begins withbs, we would get: b?(a+ab)? 11
Quiz 8, Regular GrammarsDate: April 6
1. (6pts) Convert into a regular grammar with unit productions:a?b.
4 2 1?a 3?b
P1={S1→aA1,A1→Λ}
P P
3={S3→bA3,A3→Λ}
P S
3→bA3,A3→Λ}
UsingP4as the final answer, the start symbol isS4. Note that use of the algorithm is required for this question,otherwise a very simple answer would be possible:{S→aS,S→bB,B→Λ}. 12
2. (4pts) Convert into a regular grammar without unit productions:
Solution:
S→aA
???S→BB→bB ???B→A
B→aSA→Λ
???S→A
S→bB
S→aS
S→ΛB→Λ
13 Quiz 9, Deterministic Regular GrammarsDate: April 13
1. (10pts) Convert into a deterministic regular grammar:
Solution:
ab SA,B- A BS B -A,B
S,AA,BS
S,B
A,BA,B
A,B
BS,A,B
S,A,B
A,BS,A,B
V {S}→aV{A,B} V {S}→bV∅ V {A,B}→aV{B} V {A,B}→bV{S,A,B} V {B}→aV∅ V {B}→bV{A,B} V {S,A,B}→aV{A,B} Vquotesdbs_dbs6.pdfusesText_12
[PDF] Context-Free Grammars