I'm having a hard time thinking of context free languages. The only example I've been able to think of is $0^n1^n$, but I'm having a hard time thinking of any others. Can I get some examples?
$\begingroup$
$\endgroup$
5
-
1$\begingroup$ For a start, all regular languages are context free. $\endgroup$– GoodDeedsCommented Mar 15, 2017 at 7:43
-
$\begingroup$ And we know that all regular languages must be able to be constructed by a DFA. So a language such as a^nb is not regular, right? Because n could be infinite $\endgroup$– user67794Commented Mar 15, 2017 at 7:53
-
$\begingroup$ I didn't understand your comment. $\{a^nb| n\ge0\}$ is regular, $n$ can be arbitrarily large, but for any given string, is always finite. You can construct a DFA for it. Additionally, the implication I made is one directional. A language that is not regular could still be context free, like the example in your question. $\endgroup$– GoodDeedsCommented Mar 15, 2017 at 7:58
-
$\begingroup$ If a language is regular then it's CF, correct? $\endgroup$– user67794Commented Mar 15, 2017 at 9:16
-
$\begingroup$ Below your question there is a button, marked "context-free". Click on it, and get inspired. $\endgroup$– Hendrik JanCommented Mar 15, 2017 at 11:44
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
1
Here are some of the examples of context free languages
- $\{ w \in \{0,1\}^*\mid \ w$ contains at least three ones }
- $\{ w \in \{0,1\}^*\mid \ w = w^{R}$ and $\mid w \mid $ is even }
- $\{ w \in \{0,1\}^*\mid \ $ the length of $w$ is odd and the middle symbol is $0$ }
- $\{ a^{i} b^{j} c^{k} \mid \ i,j,k \ge 0 $ and $ i + j = k $ }
- $\{ a^{i} b^{j} c^{k} \mid \ i,j,k \ge 0, $ and $ i = k $ or $i = k$ }
- $\phi$
Reference : https://web.njit.edu/~marvin/cs341/hw/hwsoln05.pdf
-
$\begingroup$ Thank you for the link to Nakayama's material. It is helpful for me studying this at a completely different university. I believe however (maybe wrong) the OP was probably interested in context free (non-regular) language examples, specifically for using them as examples in proofs or homework. For others - in Nakayama's examples above, the first one is regular while the others are not. I found this thread with almost the same question as the OP. I was looking for examples of context free languages other than the quintessential one listed. And not interested in regular. $\endgroup$– delroccoCommented Jan 29, 2019 at 21:24
$\begingroup$
$\endgroup$
More general examples of context-free languages which are not regular are the Dyck languages of balanced parentheses of several types. A 1-type Dyck language contains words such as (), (()), ()(), and so on. A 2-type Dyck language contains words such as ([]), ()[], [([()([])])[]], and so on.
The Chomsky–Schützenberger representation theorem states that, in some sense, Dyck languages are the most general type of context-free languages.
answered Mar 15, 2017 at 7:57