[PDF] [PDF] Lecture 10: Context-Free Languages Contextually Exam 1 Exam 1

[PDF] Languages that Are and Are Not Context-Free

We show that context-free languages are closed under union, concatenation, property P that all context-free languages have, and then show that L does not 

[PDF] Lecture 10: Context-Free Languages Contextually Exam 1 Exam 1

Note: unlike nearly all other sets we draw in this class, all of these sets are finite, and Proving Set Equivalence A = B ⇔ A LR(M) = the set of languages that can be LR(DFA) Deterministic Context-Free Languages: recognized by DPDA

[PDF] Context-Free Languages and Grammars - Jeff Erickson

A context-free language L is inherently ambiguous if every context-free grammar that proofs, as in every proof by induction, the inductive hypothesis is “Assume there is no smaller Prove that if L is a context-free language, then LR is also a 

[PDF] A Proof that if L = L 1 ∩ L2 where L1 is CFL and L2 is Regular then

It is well known that the intersection of a context free language and a regular language is context proof of this theorem is a cross product construction of a PDA and a DFA Def 2 1 A context free grammar is in Chomsky Normal Form if every 

[PDF] Regular and Context-Free Languages* - CORE

the grammar is used to prove several exponential lower bounds (3) Every context-sensitive language is accepted by some lba M such that for any input y all  

[PDF] CS 341 Homework 16 Languages that Are and Are Not Context-Free

Show that the following languages are context-free You can do this by writing a context free grammar or a PDA, or you can use the closure theorems for 

[PDF] Solutions to Homework 6

Assume for contradiction that is a context-free language We apply the We examine all the possible cases for the position of string 谲 /font> First we note that the string We can prove this with the pumping lemma We choose to pump  

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

If LR is a regular language and if the language L2 is context-free, then LR xy n z ∈ L for all n ≥ 0 Proof A parse tree for G generating a sufficiently long word 

[PDF] CSE 105, Fall 2019 - Homework 4 Solutions - UCSD CSE

Hence, this CFG constructs the language of all strings which start with a b Prove that L ⊂ Σ* w } LR = { R : w ∈ L the set of context-free languages is also 

[PDF] Context-Free and Noncontext-Free Languages

Theorem: The regular languages are a proper subset of Lemma: Every regular language is CF Proof: Every Techniques for showing that a language L is context-free: 1 Construct, from G, a new grammar G′, such that L(G′) = LR:

[PDF] prove that range(t + s) ⊆ range(t) + range(s).

[PDF] prove that the class of non regular languages is not closed under concatenation.

[PDF] prove that the interval (0

[PDF] prove the inverse of a bijective function is bijective

[PDF] proverbe créole martiniquais traduction

[PDF] proverbe sur apprendre de ses erreurs

[PDF] provided that logic

[PDF] providing health equity

[PDF] proview caqh sign in

[PDF] province iso codes

[PDF] provincial court notices

[PDF] provincial court office locations winnipeg

[PDF] provincial court ticket payment

[PDF] proving logical equivalence without truth tables pdf

[PDF] provisional certificate makaut

1

David Evans

http://www.cs.virginia.edu/evans cs302: Theory of Computation

University of Virginia

Computer Science

Lecture 10: Lecture 10:

ContextContext--Free Free

Languages Languages

ContextuallyContextually

2

Lecture 10: NDPDAs/CFGs/PDAs

Exam 1

• In class, next Thursday, Feb 28 • Covers:

Lectures 1-10

Sipser Ch 0-2

Problem Sets 1-3 + Comments

Exam 1

Note: unlike nearly all other sets we draw in this class, all of these sets are finite, and the size represents the relative size. 3

Lecture 10: NDPDAs/CFGs/PDAs

Exam 1 Notesheet

• For Exam 1, you may not use anything other than -Your own brain and body -A single page (one side) of notes that you create • You can work with others to create your notes page 4

Lecture 10: NDPDAs/CFGs/PDAs

Menu • Are DPDAs equivalent to NDPDAs? • Properties of CFLs • Equivalence of CFGs and

NDPDAs

5

Lecture 10: NDPDAs/CFGs/PDAs

Language Classes

Regular Languages

Context-Free Languages

Violates Pumping

L emma For RLs

Violates

P umping Lemma F or CFLs

Described by DFA, NFA,

RegExp, RegGram

Described by CFG,

N DPDA

0n1n0n1n2n

0n www Rww

Where are DPDAs?

6

Lecture 10: NDPDAs/CFGs/PDAs

Proving Set Equivalence

A= B?A ?Band B?A

Sets Aand Bare equivalent if Ais a

subset of Band Bis a subset of A. 2 7

Lecture 10: NDPDAs/CFGs/PDAs

Proving Formalism Equivalence

LR(M)= the set of languages that can be

recognized by someM = { l | l ?P(Σ*)and there is some m ?M such that L(m) = l}

A= B?LR(A) ?LR(B) and LR(B) ?LR(A)

8

Lecture 10: NDPDAs/CFGs/PDAs

Proving Formalism

Non-Equivalence

LR(M)= the set of languages that can be

recognized by someM = { l | l ?P(Σ*)and there is some m ?M such that L(m) = l}

A≠B?There is anl ?P(Σ*) that is in

LR(A) but not inLR(B)

or there is anl inLR(B) but not in LR(A) 9

Lecture 10: NDPDAs/CFGs/PDAs

Regular Languages

Context-Free Languages

Violates Pumping

L emma For RLs

Described by DFA, NFA,

RegExp, RegGram

Described by CFG,

N DPDA

0n1n0n1n2n

0n www R ww Sensible option 1: LR(NDPDA) ????LR(DPDA) ????LR(NFA) =LR(DFA) Sensible option 2: LR(NDPDA) =LR(DPDA) ????LR(NFA) =LR(DFA) To eliminate =, we need to find some language L that can be recognized by an NDPDA and prove it cannot be recognized by a DPDA 10

Lecture 10: NDPDAs/CFGs/PDAs

LR(NDPDA) ?LR(DPDA)

A= { 0i1j| i ≥0, j= ior j= 2i}

A?LR(NDPDA)

0, ε→+

1, +→εε, $ →ε

1, +→ε

1, ε→ε

11

Lecture 10: NDPDAs/CFGs/PDAs

LR(NDPDA) ?LR(DPDA)

A= { 0i1j| i ≥0, j= ior j= 2i}

A ????LR(DPDA)

Proof by contradiction.

Suppose there is a DPDA P that recognizes A.

It must be in accept states only after processing 0i1iand 0i12i ...0, α→β1, α→β

2itransitions, consuming 0i1i

...1, α→β1, α→β itransitions, consuming 1i 12

Lecture 10: NDPDAs/CFGs/PDAs

LR(NDPDA) ?LR(DPDA)

A= { 0i1j| i ≥0, j= ior j= 2i}

A ????LR(DPDA)

Proof by contradiction.

Suppose there is a DPDA P that recognizes A.

It must be in accept states only after processing 0i1iand 0i12i ...0, α→β1, α→β

2itransitions, consuming 0i1i

...1, α→β1, α→β itransitions, consuming 2i 22

L(P') = { 0i1i2i| i ≥0}

3 13

Lecture 10: NDPDAs/CFGs/PDAs

LR(NDPDA) ?LR(DPDA)

A= { 0i1j| i ≥0, j= ior j= 2i}

A ????LR(DPDA)

Proof by contradiction.If there is a DPDA Pthat

recognizes A, we could construct a DPDA P'that recognizes

A'= L(P') = { 0i1i2i| i ≥0}

But, we know A'is not a CFL! (Prove using pumping lemma) So, there is no NDPDA that can recognize A', so there is no

DPDA that can recognize A', so P'must not exist.

Hence, Pmust not exist. This means there is no DPDA that can recognize A. 14

Lecture 10: NDPDAs/CFGs/PDAs

Regular Languages

Context-Free Languages

Violates Pumping

L emma For RLs

Described by DFA, NFA,

RegExp, RegGram

Described by CFG,

N DPDA

0n1n0n1n2n

0n wA ww

LR(NDPDA) ????LR(DPDA) ????LR(NFA) =LR(DFA)

Deterministic Context-Free Languages: recognized by DPDA

A= { 0i1j| i ≥0, j= ior j= 2i}

15

Lecture 10: NDPDAs/CFGs/PDAs

Closure Properties of RLs

If Aand Bare regular languages then:

A

Ris a regular language

Construct the reverse NFA

A *is a regular language

Add a transition from accept states to start

Ais a regular language (complement)

F' = Q-F

A?Bis a regular language

Construct an NFA that combines DFAs

A ∩Bis a regular language

Construct an DFA combining DFAs that

accepts if both accept 16

Lecture 10: NDPDAs/CFGs/PDAs

Closure Properties of CFLs

If Aand Bare

context freelanguages then: A

Ris a context-free language ?

A *is a context-free language ?

Ais a context-free language (complement)?

A?Bis a context-free language ?

A ∩Bis a context-free language ?

Some of these are true. Some of them are false.

17

Lecture 10: NDPDAs/CFGs/PDAs

CFLs Closed Under Reverse

Given a CFL A, is ARa CFL?

Since Ais a CFL, there is some CFG Gthat recognizes A.

Proof-by-construction:

There is a CFG GRthat recognizes AR.

quotesdbs_dbs17.pdfusesText_23