Use LEFT and RIGHT arrow keys to navigate between flashcards;
Use UP and DOWN arrow keys to flip the card;
H to show hint;
A reads text to speech;
8 Cards in this Set
- Front
- Back
|
Define a grammar for the following: 1. a* 2. (a|b)* 3. a* | b* 4. a*b 5. ba* 6. (ab)* |
1. S -> aS | ε 2. S -> aS | bS | ε 3. S -> A | B | ε A -> aA | a B -> bB | b 4. S -> aS | b 5. S -> bA A -> aA | ε 6. S -> abS | ε |
|
|
How do you convert a grammar to a NFA? |
1. Transform all productions to the form of A -> x or A -> xB 2. q0 is the grammar's start symbol 3. for each production A -> bB make a transition qa -> qb labelled with b 4. for each production A -> B make a transition qa -> qb labelled with ε 5. productions that are A -> a go to a final state |
|
|
What are the two ways grammars are used? |
1. Verify that a given string is grammatical / parse given string 2. To generate strings that fit in the grammar (derivations) |
|
|
A string 𝛿 ∈ ( V U Σ*) is said to be in sentential form of G if... |
there exists a derivation from S -> 𝛿 |
|
|
What is the seven tuple defined by a PDA? |
A= (Q;Σ;Γ;𝛿;q0;Z;F) Q = set of states; Σ = alphabet; Γ = set of stack symbols; 𝛿 = transitions; q0 = start state; Z = end of stack symbol; F = set of final states |
|
|
What are the two kinds of CFGs that can be efficiently parsed and guarantee non-ambiguity? |
LL(k) grammars: Require aLeft-to-right scan with k token look-ahead and generate the Left-most derivationI LR(k) grammars: Require aLeft-to-right scan with k tokens look-ahead and generate the Right-most derivation |
|
|
How do you know if something is LL(1) |
If there is more than one production for the leftmost non-terminal, the correct choice is indicated by the next input symbol. |
|
|
What is this an example of? E -> E + T |
left recursion |
