Term
| Describe the components of a Context Free Grammer. |
|
Definition
Productions - The rules of the grammar.
Variables - The left hand side of the Productions. Can also be found on the right hand side. Usually denoted as upper-case.
Terminals - On the right hand side of the production. Usually denoted as lowercase. |
|
|
Term
| Any language that can be generated by some context-free grammer is called a ______ |
|
Definition
|
|
Term
| Define a Context-Free Grammer |
|
Definition
A context free grammar is a 4-tuple (V, Σ, R, S), where
1. V is a finite set called the variables
2. Σ is a finite set, disjoint from V, called the terminals
3. R is a finite set of rules, with each rule being a variable and a string of variables and terminals
4. S exists in V is the start variable |
|
|
Term
| How do you create a CFG from a RL? |
|
Definition
| Make a variable Ri for each state qi of the DFA. Add the rule Ri -> aRj to the CFG is delta(qi, a) = qj is a transition in the DFA. Add the rule Ri -> epsilon if qi is an accept state of the DFA. Make R0 the start variable of the grammar, where q0 is the start state of the machine. |
|
|
Term
| Define Chomsky Normal Form |
|
Definition
A context-free gramar is in Chomsky normal form if every rule is of the form
A->BC
A->a
where a is any terminal and A, B, C are any variables--except that B and C may not be the start variable. In addition we pemrit the rule S -> epsilon, where S is the start variable. |
|
|
Term
| Describe the algorithim to put a CFG in chomsky normal form. |
|
Definition
1. Add a new start rule S0 -> S
2. Remove epsilon rules A->epsilon, where A is not the start variable. Then for each occurence of an A on the right-hand side of a rule, we add a new rule with that occurrence deleted.
3. Remove unit rules A->B by deleting the rule and then replacing all occurences of B with the actual rule of B
4. Repeat these steps until none remain.
5. Convert remaining rules into proper form. Replace each rule A->u1u2...uk where k>=3 and each ui is a variable/terminal, with the rule A->u1A1, A1->u2A2, A2->u3A3,..., Ak-2 -> uk-1uk |
|
|
Term
| Define a pushdown automaton |
|
Definition
A pushdown automaton is a 6-tuple(Q, Σ, Γ, δ, q0, F)
1. Q is the set of states
2. Σ is the input alphabet
3. Γ is the stack alphabet
4. : Q x Σep x Γep -->P(Q x Γep) is the transition function
5. q0 exists in Q is the start state
6. F subset of Q is the set of accept states |
|
|
Term
| Define the pumping lemma for context free languages |
|
Definition
If A is a context free language, then there is a number p (the pumping length) where, if s is any string in A of length at least p, then s may be divided into five pieces s=uvxyz satisfying the conditions
1. for each i>=0, uv^ixy^iz >=0, uv^ixy^iz exists in A
2. |vy| > 0
3. |vxy| <=p |
|
|
