Ch 2 : Context Free Languages

Question 1

What capability does a context free grammar bring that was not available in a regular langauge?

Answer 1

They can describe certain features that have a recursive structure.

Question 2

Describe what a context-free language is

Answer 2

It is the collection of languages associated with context-free grammars.

It includes all the regular languages, and many others.

Context free languages are recognized by pushdown automata

Question 3

What is a substitution rule?

Answer 3

also called a production, it is written with the symbol left of the arrow indicating a variable and a string on the right side of the arrow, the string on the right side can be terminals or other variables, including the one on the left side of the arrow. The terminals are analogous to the input alphabet. At the leftmost part of the top rule is the start variable.

Question 4

What is a derivation?

Answer 4

the sequence of substitutions to obtain a string. can be shown pictorially with a parse tree, or via derivation type writing. Start with the top variable, continually replace all the variables on the right with the corresponding right side of a rule that has that variable on the left. Keep doing that until there are no variables left. All that remains will be a string. That string was derived from the grammar

Question 5

What is a language of a grammar?

Answer 5

It is all strings that are generated in the way we described the derivation above.

Question 6

What is a grammar?

Answer 6

A list of rules containing variables and terminals. The terminals are the input string and the variables are how you can replace symbols according to the rules (?)

Question 7

What are the book’s four tips for constructing CFG’s?

Answer 7

1. Break into smaller pieces and ‘or’ together.
2. Construct a DFA if its regular and convert
3. Remember how two substrings are linked and the machine has to remember one to get the other
4. Remember recursion and place variables where they are recursively referenced.

Question 8

What does it mean for a grammar to be ambiguous?

Answer 8

It derives the same string in different ways, in other words, it has two or more left-most derivations or parse trees.

Because the derivations could be different based on the orders of the variable replacement, really we mean the parse trees and thus throw down with left most as the standard.

Question 9

What is Chomsky normal form?

Answer 9

Every rule in a CNF is of the form:
A -> BC
A -> a

(BC cannot be the start variable, also S-> epsilon is legit)

Question 10

What are the steps to convert to Chomsky Normal Form?

Answer 10

1. Add new start variable
2. Take care of all epsilon rules
3. Handle all unit rules
4. Convert all remaining to proper form

Question 11

What are steps for creating a PDA from a CFL/CFG?

Answer 11

1. put $ on top of stack
2. Repeat forever…..
   a. if top of stack is a $, enter accept (accepts the input if it’s all been read)
   b. if top of stack is a terminal, read the next input and match it. continue if matches, fail if not.
   c. if top of stack is a variable, nondeterministically select one of the rules for A and substitute it with one of the rules on the right side of A.

Question 12

How do I prove a language is non-regular?

Answer 12

Use the pumping lemma….. see those cards

Question 13

What is a DPDA? Why does it matter, where is it used, what does it tell us?

Answer 13

Deterministic Push Down Automata.

Unlike DFA’s and NFA’s which are equivalent, PDA’s are not equivalent across DPDA’s and NPDA’s.

But DPDA’s are really practical especially in parsers for programming languages.

DPDA’s have at most one way of moving forward (no choice, or guess).

Question 14

What is the language called that represents a DPDA>

Answer 14

A deterministic context-free language.

Question 15

Are all CFL’s DCFL’s?

Answer 15

No, absolutely not. Any CFL whose complement isn’t a a CFL isn’t a DCFL

Question 16

What is the meaning and use of end markers?

Answer 16

A is a DCFL if and only if A -| is a DCFL. Adding end markers doesn’t change the power of DPDA’s, however, designing DPDA’s on endmarked inputs is often easier because we take advantage of knowing when the string ends.

Question 17

What is the relationship between DCFG and DPDA’s

Answer 17

They are equivalent provided that we restrict our atttentionto endmarked languages. The equivalence does NOT hold without the endmarkers.

Question 18

How does defining DCFG’s differ from deriving CFG’s?

Answer 18

They go from the bottom up.

Question 19

What is a reduce step? How does it relate to a substitution?

Answer 19

A reduction is the entire process of reversed derivations. Basically a reduce step is a reversed substitution.

strings of terminals from the right side are replaced by the variable on the corresponding left hand side.

Question 20

How do reductions and reverse derivations relate?

Answer 20

A leftmost reduction is a right most derivation in reverse.

Question 21

What is a handle?

What is a valid string?

Answer 21

h, which is the reducing string in a in leftmost reduction of w, which is the equivalent of T-> h is applied in reverse.

h, together with its reducing rule T is called the handle.

A valid string is a string that appears in a leftmost reduction of some string in L(G)

Question 22

How do handles relate to ambiguity?

Answer 22

If a grammar is ambiguous, a valid string can have several handles. For unambiguous grammars, the left most reductions, (only one parse tree) are unique, as well as the handles.

Question 23

How are handles related to the definition of deterministic context free grammars?

Answer 23

As we read from left to right, once we’ve seen the handle, we have to KNOW it. and we don’t need to read beyond. A handle is a forced handle if h is the unique handle in every valid string xhy

A DCFG is a CFG such that every valid string has a forced handle.

Question 24

Pickup again on page 139

Answer 24

….[INSERT]

Question 25

What is the definition of a string being a prefix, a proper prefix, and a language being prefix free?

Answer 25

First, a language is just a set of strings.

x is a prefix of y if z exists such that xz = y….

x is a proper prefix if x != y

A language is prefix-free if no member is a proper prefix of another member.

Question 26

What is a deterministic context free grammar?

Answer 26

DCFG’s are those who’s reductions have a certain property. That property is that every valid string has a forced handle.

A DCFG is a CFG such that every string has a forced handel.

Question 27

What is the definition of a context free grammar?

Answer 27

The 4-tuple of the following …

(V, E, R, S)

V : finite set of variables
E : finite set of terminals disjoint from V
R is a finite set of rules, each rule being a variable and a string of variables and terminals
S is the start variable.

Question 28

Why are grammars called context free?

Answer 28

Derivation of single step does not depend on context of occurrence of a given variable.

Question 29

𝑢𝐴𝑣⇒𝑢𝑤𝑣 (𝑢𝐴𝑣 yields 𝑢𝑤𝑣): 𝑢,𝑣∈(𝑉 ∪ Σ)*, 𝐴→𝑤 a production of 𝐺

Answer 29

A derives w, and we do it in any context, u v, we can do it the same in any context. This is why called context free.

Question 30

𝐿𝐺=𝑤∈Σ∗𝑆∗⇒𝑤} the language generated by the context free grammar 𝐺

Answer 30

Language of our grammar consists of those terminal strings which can be derived in some finite amount of steps out of the start symbol

Question 31

Does CNF remove ambiguity?

Answer 31

No, as any grammar can be put in CNF

Question 32

How’s a PDA like an NFA?

Answer 32

A PDA is a NFA with a stack

Question 33

What implications and inclusions do we need to show to prove that we’ve got appropriate and equivalent (PDA/NFA, etc.)

Answer 33

1. If string is of that form, then our PDA/NFA accepts…

2. If our PDA/NFA accepts, then our string is of that form.