[PDF] Homework 6 Solutions Note that A is a

View - Download Homework 6 Solutions

Previous PDF

Next PDF

CS 341: Foundations of Computer Science II

Prof. Marvin Nakayama

Homework 6 Solutions

1. Give pushdown automata that recognize the following languages.Give both a drawing

and6-tuple specification for each PDA. (a)A={w? {0,1}?|wcontains at least three1s}

Answer:

q1q2q3q4

0, ε→ε

1, ε→ε

0, ε→ε

1, ε→ε

0, ε→ε

1, ε→ε

0, ε→ε

1, ε→ε

We formally express the PDA as a 6-tuple(Q,Σ,Γ,δ,q1,F), where •Q={q1,q2,q3,q4} •Σ ={0,1} •Γ ={0,1} •transition functionδ:Q×Σε×Γε→ P(Q×Γε)is defined by

Input:01ε

Stack:01ε01ε01ε

q1{(q1,ε)}{(q2,ε)} q2{(q2,ε)}{(q3,ε)} q3{(q3,ε)}{(q4,ε)} q4{(q4,ε)}{(q4,ε)}

Blank entries are∅.

•q1is the start state •F={q4} Note thatAis a regular language, so the language has a DFA. We can easily convert the DFA into a PDA by using the same states and transitionsand never push nor pop anything to/from the stack. 1 (b)B={w? {0,1}?|w=wRand the length ofwis odd}

Answer:

q1q2q3q4ε, ε→$

0, ε→0

1, ε→1

0, ε→ε

1, ε→ε

0,0→ε

1,1→ε

Since the length of any stringw?Bis odd,wmust have a symbol exactly in the middle position; i.e.,|w|= 2n+ 1for somen≥0, and the(n+ 1)th symbol inwis the middle one. If a stringwof length2n+ 1satisfiesw=wR, the firstnsymbols must match (in reverse order) the lastnsymbols, and the middle symbol doesn"t have to match anything. Thus, in the above PDA, the transition fromq2to itself reads the firstnsymbols and pushes these on the stack. The transition fromq2toq3nondeterministically identifies the middle symbol ofw, which doesn"t need to match any symbol, so the stack is unaltered. The transition fromq3to itself then reads the lastnsymbols ofw, popping the stack at each step to make sure the symbols after the middle match (in reverse order)the symbols before the middle. We formally express the PDA as a 6-tuple(Q,Σ,Γ,δ,q1,F), where •Q={q1,q2,q3,q4} •Σ ={0,1} •Γ ={0,1,$}(use$to mark bottom of stack) •transition functionδ:Q×Σε×Γε→ P(Q×Γε)is defined by

Input:01ε

Stack:01$ε01$ε01$ε

q1{(q2,$)} q2{(q2,0),(q3,ε)}{(q2,1),(q3,ε)} q3{(q3,ε)}{(q3,ε)}{(q4,ε)} q4

Blank entries are∅.

•q1is the start state •F={q4} (c)C={w? {0,1}?|w=wR}

Answer:

2 q1q2q3q4ε, ε→$

0, ε→0

1, ε→1

0, ε→ε

1, ε→ε

0,0→ε

1,1→ε

The length of a stringw?Ccan be either even or odd. If it"s even, then there is no middle symbol inw, so the first half ofwis pushed on the stack, we move fromq2toq3without reading, pushing, or popping anything, and then match the second half ofwto the first half in reverse order by popping the stack. If the length ofwis odd, then there is a middle symbol inw, and the description of the

PDA in part (b) applies.

We formally express the PDA as a 6-tuple(Q,Σ,Γ,δ,q1,F), where •Q={q1,q2,q3,q4} •Σ ={0,1} •Γ ={0,1,$}(use$to mark bottom of stack) •transition functionδ:Q×Σε×Γε→ P(Q×Γε)is defined by

Input:01ε

Stack:01$ε01$ε01$ε

q1{(q2,$)} q3{(q3,ε)}{(q3,ε)}{(q4,ε)} q4

Blank entries are∅.

•q1is the start state •F={q1,q4} (d)D={aibjck|i,j,k≥0, andi=jorj=k}

Answer:

q1 q2q3q4 q5q6q7q8 a, ε→ab, a→ε c, ε→ε a, ε→ε b, ε→bc, b→ε 3 The PDA has a nondeterministic branch atq1. If the string isaibjckwithi=j, then the PDA takes the branch fromq1toq2. If the string isaibjckwithj=k, then the PDA takes the branch fromq1toq5. We formally express the PDA as a 6-tuple(Q,Σ,Γ,δ,q1,F), where •Q={q1,q2,...,q8} •Σ ={a,b,c} •Γ ={a,b,$}(use$to mark bottom of stack) •transition functionδ:Q×Σε×Γε→ P(Q×Γε)is defined by

Input:abcε

Stack:abc$εabc$εabc$εabc$ε

q1{(q2,$),(q5,$)} q2{(q2,a)}{(q3,ε)} q3{(q3,ε)}{(q4,ε)} q4{(q4,ε)} q5{(q5,ε)}{(q6,ε)} q6{(q6,b)}{(q7,ε)} q7{(q7,ε)}{(q8,ε)} q8

Blank entries are∅.

•q1is the start state •F={q4,q8} (e)E={aibjck|i,j,k≥0andi+j=k}

Answer:

q1q2q3q4q5ε, ε→$ε, ε→ε a, ε→xb, ε→x c, x→ε For everyaandbread in the first part of the string, the PDA pushes anxonto the stack. Then it must read acfor eachxpopped off the stack. We formally express the PDA as a 6-tuple(Q,Σ,Γ,δ,q1,F), where •Q={q1,q2,...,q5} •Σ ={a,b,c} •Γ ={x,$}(use$to mark bottom of stack) •transition functionδ:Q×Σε×Γε→ P(Q×Γε)is defined by

Input:abcε

Stack:x$εx$εx$εx$ε

q1{(q2,$)} q2{(q2,x)}{(q3,ε)} q3{(q3,x)}{(q4,ε)} q4{(q4,ε)}{(q5,ε)} q5 4

Blank entries are∅.

•q1is the start state •F={q5} (f)F={a2nb3n|n≥0}

Answer:

q1q2 q3 q4 q5q6 q7ε, ε→$ a, ε→εa, ε→x b, ε→ε b, ε→ε b, x→ε The PDA pushes a singlexonto the stack for every 2a"s read at the beginning of the string. Then it pops a singlexfor every 3b"s read at the end of the string. We formally express the PDA as a 6-tuple(Q,Σ,Γ,δ,q1,F), where •Q={q1,q2,...,q7} •Σ ={a,b} •Γ ={x,$}(use$to mark bottom of stack) •transition functionδ:Q×Σε×Γε→ P(Q×Γε)is defined by

Input:abε

Stack:x$εx$εx$ε

q1{(q2,$)} q2{(q3,ε)}{(q4,ε)} q3{(q2,x)} q4{(q5,ε)}{(q7,ε)} q5{(q6,ε)} q6{(q4,ε)} q7

Blank entries are∅.

•q1is the start state •F={q7} (g)L={aibjck|i,j,k≥0andi+k=j}quotesdbs_dbs2.pdfusesText_3

[PDF] language homework q4 2

[PDF] language homework q4 4

[PDF] language learning in early childhood pdf

[PDF] language model

[PDF] language of drama pdf

[PDF] language processing disorder in adults

[PDF] language processing disorder test

[PDF] language proficiency meaning

[PDF] language proficiency test series (lpts)

[PDF] language rating scale

[PDF] language st unity pro

[PDF] language studies international ltd

[PDF] languages and locales

[PDF] languages in automata theory

[PDF] languages in discrete mathematics