[PDF] [PDF] Homework 6 Solutions

[PDF] Homework 6 Solutions

Give pushdown automata that recognize the following languages Give both a drawing and 6-tuple specification for each PDA (a) A = { w ∈ {0, 1} 

[PDF] Solutions for Homework Five, CSE 355 - publicasuedu

c) Trace all computations of the strings aab, abb, aba in M d) Show that aabb, aaab ∈ L(M) Solution: a) The PDA M accepts the language { 

[PDF] Pushdown Automata Exercises - LIACS

We start with standard problems on building pda for a given language, ending with more Solutions 1a The pda is depicted by the following diagram Formally  

[PDF] Pushdown Automata (PDA)

Q) Does a PDA that accepts by empty stack need any final state specified in the design? Page 15 Example: L of balanced p parenthesis PDA that 

[PDF] Context-Free Languages and Pushdown Automata - IGM

and also provide some examples or counter-examples for researchers This section with two results: one concerning the pushdown store language of a pda , the may indeed be de ned as the components of the least solution of systems

[PDF] Pushdown Automata

A pushdown automaton (PDA) is a finite automaton equipped with a stack-based memory ○ Each transition ○ is based on the current input symbol and the top 

[PDF] Chapter 4 Pushdown automata and context-free languages

An execution of a pushdown automaton on a word w is a sequence of configurations Solution: Grammar satisfying the following constraints 1 A → σ with σ 

[PDF] pushkit apns

[PDF] pushq assembly

[PDF] put my paper in apa format

[PDF] putlockers

[PDF] putnam county school calendar 2020 2021

[PDF] putting a price on carbon cdp

[PDF] pvc dwv fittings

[PDF] pvif table

[PDF] pvifa table

[PDF] pwc cfa reimbursement

[PDF] pwc cybersecurity report 2019

[PDF] pwc global

[PDF] pwc global fintech report 2019

[PDF] pwc tax calculator france

[PDF] pwd karnataka

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,$)} q2{(q2,0),(q3,ε)}{(q2,1),(q3,ε)}{(q3,ε)} 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ε

quotesdbs_dbs2.pdfusesText_2