Exercises on context-free grammars (CFG)

  1. Unambiguous CFG for {anbn∣n≥0}\{ a^n b^n \mid n\geq 0 \}
  2. Unambiguous CFG for {ancbn∣n>0}\{ a^n c b^n \mid n>0 \}
  3. Unambiguous CFG for {aibj∣i≥j}\{ a^i b^j \mid i\geq j \}
  4. Unambiguous CFG for {aibj∣i≤j}\{ a^i b^j \mid i\leq j \}
  5. Unambiguous CFG for {aibj∣2i≤j}\{ a^i b^j \mid 2i\leq j \}
  6. CFG for {aibj∣2i≥j}\{ a^i b^j \mid 2i\geq j \}
  7. Unambiguous CFG for {aibj∣2i≥j}\{ a^i b^j \mid 2i\geq j \}
  8. Unambiguous CFG for {aibj∣j≤i≤2j}\{ a^i b^j \mid j\leq i\leq 2j \}
  9. Unambiguous CFG for {aibj∣i≥j∨i≤2j}\{ a^i b^j \mid i\geq j \vee i\leq 2j \}
  10. Unambiguous CFG for {aibjck∣i=j+k}\{ a^i b^j c^k \mid i=j+k \}
  11. Unambiguous CFG for {aibjck∣j=i+k}\{ a^i b^j c^k \mid j=i+k \}
  12. CFG for {aibjck∣i=j∨j=k∨i=k}\{ a^i b^j c^k \mid i=j \vee j=k \vee i=k \}
  13. CFG for {an0ban1b…anm−1banm∣m≥1∧∃i∈{1,…,m}:(n0=ni)}\{ a^{n_0} b a^{n_1} b \ldots a^{n_{m-1}} b a^{n_m} \mid m\geq 1 \wedge \exists i\in\{1,\ldots,m\}: (n_0 = n_i) \}
  14. Unambiguous CFG for {an0ban1b…anm−1banm∣m≥1∧(n0=∑1≤i≤mni)}\{ a^{n_0} b a^{n_1} b \ldots a^{n_{m-1}} b a^{n_m} \mid m\geq 1 \wedge (n_0 = \sum_{1\leq i\leq m} n_i) \}
  15. CFG for {an0ban1b…anm−1banm∣m≥1∧∃I⊆{1,…,m}:(n0=∑i∈Ini)}\{ a^{n_0} b a^{n_1} b \ldots a^{n_{m-1}} b a^{n_m} \mid m\geq 1 \wedge \exists I\subseteq\{1,\ldots,m\}: (n_0 = \sum_{i\in I} n_i) \}
  16. Unambiguous CFG for {w∈{a,b}∗∣w=wR}\{ w \in \{a,b\}^* \mid w=w^R \}
  17. Unambiguous CFG for {w∈{a,b}∗∣w=wR∧∣w∣aba=0}\{ w \in \{a,b\}^* \mid w=w^R \wedge |w|_{aba}=0 \}
  18. Unambiguous CFG for {w∈{a,b}∗∣w=wR∧∣w∣a>0∧∣w∣b>0}\{ w \in \{a,b\}^* \mid w=w^R \wedge |w|_a>0 \wedge |w|_b>0 \}
  19. Unambiguous CFG for {w∈{a,b}∗∣w=wR∧∣w∣aba>0}\{ w \in \{a,b\}^* \mid w=w^R \wedge |w|_{aba}>0 \}
  20. CFG for the well-parenthesized words over {(,)}\{ ( , ) \}
  21. CFG for the well-parenthesized words over {[,],(,)}\{ [ , ] , ( , ) \}
  22. Unambiguous CFG for the well-parenthesized words over {(,)}\{ ( , ) \}
  23. Unambiguous CFG for the well-parenthesized words over {[,],(,)}\{ [ , ] , ( , ) \}
  24. CFG for {w∈{a,b}∗∣∣w∣a=∣w∣b}\{ w \in \{a,b\}^* \mid |w|_a=|w|_b \}
  25. CFG for {w∈{a,b,c}∗∣∣w∣a=∣w∣b}\{ w \in \{a,b,c\}^* \mid |w|_a=|w|_b \}
  26. CFG for {w∈{a,b,c}∗∣∣w∣a+∣w∣b=∣w∣c}\{ w \in \{a,b,c\}^* \mid |w|_a+|w|_b=|w|_c \}
  27. CFG for {w∈{a,b}∗∣2∣w∣a=∣w∣b}\{ w \in \{a,b\}^* \mid 2|w|_a=|w|_b \}
  28. Unambiguous CFG for {w∈{a,b}∗∣∣w∣a=∣w∣b}\{ w \in \{a,b\}^* \mid |w|_a=|w|_b \}
  29. Unambiguous CFG for {w∈{a,b,c}∗∣∣w∣a=∣w∣b}\{ w \in \{a,b,c\}^* \mid |w|_a=|w|_b \}
  30. Unambiguous CFG for {w∈{a,b,c}∗∣∣w∣a+∣w∣b=∣w∣c}\{ w \in \{a,b,c\}^* \mid |w|_a+|w|_b=|w|_c \}
  31. Unambiguous CFG for {w∈{a,b}∗∣2∣w∣a=∣w∣b}\{ w \in \{a,b\}^* \mid 2|w|_a=|w|_b \}
  32. Unambiguous CFG for {xcy∣x,y∈{a,b}∗∧∣x∣a=∣y∣b}\{ xcy \mid x,y\in\{a,b\}^* \wedge |x|_a=|y|_b \}
  33. Unambiguous CFG for {xcy∣x,y∈{a,b}∗∧∣x∣ab=∣y∣ba}\{ xcy \mid x,y\in\{a,b\}^* \wedge |x|_{ab}=|y|_{ba} \}
  34. Unambiguous CFG for {xcy∣x,y∈{a,b}∗∧∣x∣aba=∣y∣bab}\{ xcy \mid x,y\in\{a,b\}^* \wedge |x|_{aba}=|y|_{bab} \}
  35. Unambiguous CFG for {xcy∣x,y∈{a,b}∗∧yR prefix of x}\{ xcy \mid x,y\in\{a,b\}^* \wedge y^R \text{ prefix of } x \}
  36. Unambiguous CFG for {xcy∣x,y∈{a,b}∗∧yR suffix of x}\{ xcy \mid x,y\in\{a,b\}^* \wedge y^R \text{ suffix of } x \}
  37. Unambiguous CFG for {xcy∣x,y∈{a,b}∗∧∣x∣=∣y∣∧∣x∣aa>0}\{ xcy \mid x,y\in\{a,b\}^* \wedge |x|=|y| \wedge |x|_{aa}>0 \}
  38. CFG for the complement of {anbn∣n≥0}\{ a^n b^n \mid n\geq 0 \}
  39. Unambiguous CFG for the complement of {anbn∣n≥0}\{ a^n b^n \mid n\geq 0 \}
  40. Unambiguous CFG for the complement of {w∈{a,b}∗∣w=wR}\{ w \in \{a,b\}^* \mid w=w^R \}
  41. CFG for the complement of {anbncn∣n≥0}\{ a^n b^n c^n \mid n\geq 0 \}
  42. CFG for the complement of {wcw∣w∈{a,b}∗}\{ wcw \mid w\in\{a,b\}^* \}
  43. CFG for expressions over {+,−,∗,/,(,),0,1,…,9}\{ + , - , * , / , ( , ) , 0 , 1, \ldots, 9 \}
  44. Unambiguous CFG for expressions over {+,−,∗,/,(,),0,1,…,9}\{ + , - , * , / , ( , ) , 0 , 1, \ldots, 9 \}
  45. CFG for {anbmckdt∣n=m∨n=k∨n=t}\{ a^n b^m c^k d^t \mid n=m \vee n=k \vee n=t \}