**Heads Up!**Please do not by heart this table. This is just to check your understanding

Grammar | $w \in L(G)$ | $L(G) = \phi$ | $L(G) = \Sigma^*$ | $L(G_1) \subseteq L(G_2)$ | $L(G_1) = L(G_2)$ | $L(G_1) \cap L(G_2) = \phi$ | $L(G)$ is regular? | $L(G)$ is finite? |
---|---|---|---|---|---|---|---|---|

Regular Grammar | D | D | D | D | D | D | D | D |

Det. Context Free | D | D | D | UD | D | UD | D | D |

Context Free | D | D | UD | UD | UD | UD | UD | D |

Context Sensitive | D | UD | UD | UD | UD | UD | UD | UD |

Recursive | D | UD | UD | UD | UD | UD | UD | UD |

Recursively Enumerable | UD | UD | UD | UD | UD | UD | UD | UD |

Checking if $L(CFG)$ is finite is decidable because we just need to see if $L(CFG)$ contains any string with length between $n$ and $2n-1$, where $n$ is the pumping lemma constant. If so, $L(CFG)$ is infinite otherwise it is finite.

44,924 total views, 13 views today