1. Construct Mealy machine that corresponds to the following circuit.
Input A
OR
DELAY
B Output
AND
NAND
Bnew = Aold
Anew = Input OR (Aold NAND Bold) Output = Aold AND (Aold NAND Bold)
State Input = 0
Aold Bold Anew Bnew q0 0 0 1 0 q1 0 1 1 0 q2 1 0 1 1 q3 1 1 0 1
q0 q1
0/0
q2 q3
new state =q2
=q2
=q3
=q1
Input = 1 Output Anew Bnew
0 1 0 0 1 0 1 1 1 0 1 1
new state
=q2 0 =q2 0 =q3 1 =q3 0
Output
0/1, 1/0
0/1, 1/1
1/0, 0/0
https://www.coursehero.com/file/10256988/CSI-3104-Winter-2007-Final-Exam-So1lutions/
1/0
This study resource was shared via CourseHero.com
2. Construct a CFL which generates the language L = {ambn,3n ≥ m ≥ n ≥ 1}.
S → aSb | aaSb | aaaSb | ab | aab | aaab
3. Prove that L = {ambn,3n ≥ m ≥ n ≥ 1} is a nonregular language.
Proof: Let A be a finite automaton for L with k states. Consider words for m > k. Let ap and aq finishinthesamestate, p
Alternative Proof: Assume L is regular. Let p be the constant of the pumping lemma (which corresponds to the number of states of a finite automaton). Consider the word w = apbn with 3n ≥ p ≥ n which is in L and has a length greater than p. From the pumping lemma for regular languages follows that we can decompose w into xyz such that |y| > 0, |xy| ≤ p and for all i ≥ 0, xyiz ∈ L. From |xy| ≤ p follows that y consists only of ’a’s and the decomposition of w has the following form:
ap−q (aq)i bn (for q < p)
xyz
Now, w can be “pumped up” such that ap−q(aq)ibn ∈ L for all i ≥ 0. Choosing i = 3n violates
the condition 3n ≥ (p−q)+q·i because p ≥ n and q > 0, which is a contradiction.
https://www.coursehero.com/file/10256988/CSI-3104-Winter-2007-Final-Exam-So2lutions/
This study resource was shared via CourseHero.com
4. For the following grammar, decide whether the corresponding language is finite or infinite. Justify your answer.
S → XY
X → AA | XY | b A → BC
B → AC
C → BA
Y→a
The language is infinite, because it has useful self-embedded non-terminals. X is useful, i.e. it is used in another production (S → XY) and it is self-embedded (X → XY). Therefore, it can be used infinitely often.
5. Construct a PDA which accepts the language L = {anbn+1,n = 1,2,…}.
START
READ
a
PUSH a
READ b
b READ
a
end of input
READ Λ READ
b n+1
a
POP Λ READ empty stack
ACCEPT
(if a transition is not specified, it means reject)
https://www.coursehero.com/file/10256988/CSI-3104-Winter-2007-Final-Exam-So3lutions/
This study resource was shared via CourseHero.com
6. Is the language L = {a2nb3na4n,n = 1,2,3,…} context free? If not, prove. If yes, give a CFL that accepts it.
L is not context-free.
Proof (by contradiction): Assume L is context-free language. Let p be an sufficiently large constant. From the pumping lemma for context-free languages follows that we can decompose a word w with |w| ≥ p into w = uvxyz with |vxy| ≤ p and |vy| > 0, such that uvixyiz ∈ L for all i ≥ 0.
For words w = a2nb3na4n ∈ L with |w| > p there is no way of finding a decomposition into uvxyz, such that uvixyiz ∈ L. If in the decomposition the parts v or y contain both ’a’s and ’b’s, then they would be in the wrong order after “pumping up” the word to uvixyiz. Otherwise, if v or y contain only either ’a’s or ’b’s, then the “pumping” would cause an imbalance in the number of the let- ters: Either the number of the ’a’s on the left and/or the number ’b’s in the middle increases, but there is no chance to increase the number of the ’a’s on the right at the same time.
Example: a (aa)i abb (bbb)i baaaaaaaa
uvxy z
7. Convert the following CFL into CNF.
S → ABABAB A→a|Λ B→b|Λ
Shrink the right- hand side: S→AR1
R1 →BR2
R2 →AR3 R3 →BR4 R4→AB A→a|Λ B→b|Λ
Remove null productions: S→R1 |AR1 R1 →R2 |BR2 R2 →R3 |AR3 R3 →R4 |BR4 R4 →A|B|AB A→a|Λ B→b|Λ
Remove unit productions:
S→AR1 |BR2 |AR3 |BR4 |AB|a|b
R1 →BR2 |AR3 |BR4 |AB|a|b
R2 →AR3 |BR4 |AB|a|b
R3 →BR4 |AB|a|b
R4 →A|B|AB
A→a
B→b
(S → Λ required to obtain the original grammar)
https://www.coursehero.com/file/10256988/CSI-3104-Winter-2007-Final-Exam-So4lutions/
This study resource was shared via CourseHero.com
8. Build a TM that accepts the language L = {(ab)n(ba)n,n = 1,2,3,…}.
12
83
74
65
START
(a,Λ,R)
(b,Λ,R)
(a,Λ,R)
(Λ,Λ,R)
(a,a,L)
(a,a,R)
(Λ,Λ,L)
(a,Λ,L)
(a,a,L) (b,b,L)
(b,b,R) (a,a,R)
HALT (Λ,Λ,R)
(b,Λ,L)
Powered by TCPDF (www.tcpdf.org)
https://www.coursehero.com/file/10256988/CSI-3104-Winter-2007-Final-Exam-So5lutions/
This study resource was shared via CourseHero.com