questions about automata and formal languages
1. NFA, DFA, and RegExp In all of the subtasks below Σ = {a, b}. Figures showing the DFAs and NFAs on the last pages. (a) Make a DFA for the language accepted by the NFA in the file 1a.nfa (b) Make a DFA for the language accepted by the NFA in the file 1b.nfa (c) Make a regular expression for the language accepted by the DFA in the file 1c.dfa (d) Make a regular expression for the language accepted by the DFA in the file 1d.dfa 2. Grammars (Solve in Mentor) (a) Make a CFG for the language {apbqar : q = p+ r, p and p, r ≥ 0} (b) Make a CFG for the language accepted by the DFA in the file 2b.dfa (it is the same one as 1c.dfa!) (c) Consider the grammar G with variables {S, T,A,B}, terminals {a, b} starting symbol S and productions S → ABS | AS BA→ AB BS → Sb AS → Ta AT → Ta T → λ Make a context free grammar G′ such that L(G′) = L(G). (d) For the purposes of this task, regular expressions are defined to be the following subset of strings over the alphabet Σ = {a, b, (, ),+, ∗}: The strings “a” and “b” are regular expressions. If x ∈ Σ∗ is a regular expression then (x) and x∗ is a regular expression. If x ∈ Σ∗ and y ∈ Σ∗ are regular expressions then x+y and xy are regular expressions. Make a context free grammar that generates the language of all regular expres- sions. Here we have replaced ∪ with + since Mentor doesn’t like latex sybmols1. 1To pass non-alphanumeric characters to Mentor (like (, ), +, and *) you must put quotes around your input string. For example, running on CSIL, $∼zsisco/bin/mentor 2d.cfg accept "(ab)+a*". 2 3. Ambiguous? For each of the context free grammars below, indicate whether the grammar is am- biguous or unambiguous. If it is unambiguous give a brief justification for why. If it is ambiguous find a string s in the language generated by the grammar and draw two distinct derivation trees for s. (a) Terminals T = {a, b}, variables V = {0, 1, 2}, starting symbol S = 0, and pro- ductions 0→ 1b | 2a 1→ 2b | 0a 2→ 0b | 1a 2→ λ (b) Terminals T = {(, )}, variables V = {S}, starting symbol S, and productions S → SS | (S) | () (c) Terminals T = {a, b}, variables V = {S,K,L,M,N}, starting symbol S, and productions S → K | M K → aK | aL L→ bLa | ba M →Ma | Na N → aNb | ab (d) Terminals T = {a, b}, variables V = {S,A,B}, starting symbol S, and produc- tions S → aBABA | bABBA A→ a | bABBA B → b | aAAA 3 Figure 1: The NFA of 1a Figure 2: The NFA of 1b Figure 3: The DFA of 1c and 2b 4 Figure 4: The NFA of 1d 5