1
$\begingroup$

As far as I know, finite languages have a finite number of strings or words, while context-free languages are generated by context-free grammars. I don't know which aspect should I know that they are correlated with. All I know is that finite languages are regular, and regular languages are context-free. How should I know this?

$\endgroup$
1
  • 4
    $\begingroup$ "All I know is that finite languages are regular, and regular languages are context-free." This immediately implies that all finite languages are context-free. $\endgroup$
    – idmean
    Jan 12 at 11:09
16
$\begingroup$

The language consisting of the words $w_1,w_2,\ldots,w_n$ is generated by the context-free grammar $$ S \to w_1 \mid w_2 \mid \cdots \mid w_n. $$

$\endgroup$
3
  • $\begingroup$ So, are all finite languages context-free sir? or just some? $\endgroup$ Jan 12 at 5:49
  • 3
    $\begingroup$ @JorelleTuyor What this answer is telling you: Every finite language is regular, because it can be created with a regular grammar like above, where the words are simply exhaustively listed. So yes, every finite language is regular (and thus also context free). $\endgroup$
    – kutschkem
    Jan 12 at 7:00
  • $\begingroup$ @kutschkem Thank you for clarifying sir. God bless. $\endgroup$ Jan 12 at 7:08
1
$\begingroup$

Let

  • $F$ be the set of finite languages
  • $R$ be the set of regular languages
  • $C$ be the set of context-free languages.

The statement "All finite languages are regular" can be rewritten $F \subseteq R$. Similarly, "All regular languages are context-free" can be rewritten $R \subseteq C$. Both being true, we can take $F \subseteq R \land R \subseteq C$ to be true as well.

Set inclusion is known to be a transitive relation, that is $F \subseteq R \land R \subseteq C \rightarrow F \subseteq C$. Thus, by modus ponens, we can conclude that $F \subseteq C$ is true, or that all finite languages are context-free.

$\endgroup$
1
  • $\begingroup$ Very Well said Sir. Thanks.❤ $\endgroup$ Jan 12 at 15:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.