Mathematics Stack Exchange
Mathematics Stack Exchange

Questions tagged [context-free-grammar]

Context-free grammars give a set of rules for generating formal languages. The formal languages generated by a context-free grammar are known as context-free languages.

Context-free grammars (CFGs) were introduced by Noam Chomsky in an attempt to classify formal languages. CFGs are type-2 grammars in the Chomsky hierarchy and generate what is known as context-free languages.

Formally, CFGs consists of a set $V$ of variables, an alphabet $\Sigma$, a set of production rules $R$ and a start symbol $S \in V$.

As an example, the following CFG generates the language of all strings starting with $1$ over the alphabet $\{1,0\}$. The start symbol is $S$.

$$S \rightarrow 1B$$

$$B \rightarrow 1B \; | \; 0B \; | \; 1 \; | \; 0$$

Here the arrow means that the variable on the left-hand side can be replaced by any of the expressions on the right-hand side, where different expressions are separated by a $|$.

To derive the string $1101$ from the previous CFG, we can give the following derivation, starting with the start symbol $S$.

$$S \Rightarrow 1B \Rightarrow 11B \Rightarrow 110B \Rightarrow 1101$$

980 questions
3
votes
1 answer

Need to create a context-free language

I need to create a context-free language for the following language. $$L = \{w\in\Sigma^\ast \mid w = a^k b^m c^n \text{ where } k,m,n\in\mathbb N \text{ and } kn\}$$ Here ^ is the empty string S= aAb | AbB | bBC | aTbBbc A = aA | aAb |…
user243528
  • 31
2
votes
1 answer

Create context-free grammar for $\{w \mid |w| $ is odd with a 0 in the middle$\}$

I need to find a CFG where the word length $|w|$ is odd. Plus there must be a $0$ in the middle. In a previous exercise I had to specify a CFG only for odd word length. I chose the following: $G = (\{A,B\},\{0,1\},P,A)$ $P =\{A \to 1B \mid 0B, B \to…
Chris
  • 521
2
votes
2 answers

Find CFG for $a^i b^j c^k$ with $!(i=j=k)$

I need to show that the following language is context free: It contains all words $a^i b^j c^k$ with the condition that there're not exactly as many a's and b's and c's. I would write it like this: $$\{a^i b^j c^k\; : \;\;!(i=j=k) \;\}$$ Here's what…
ThimoKl
  • 123
2
votes
2 answers

Find the CFG for $a^n b^m c^k$

I have a language like this and will need to write the Context-free grammar for it. $$\{a^n b^m c^k\; : \;k = |n-m|,\; m, n, k \geq 0\}$$ What I am confused is do I need to simplify the condition of k = |n-m| to solve or it just means the length
Herious
  • 157
2
votes
2 answers

Find context free grammar for $u v w v^R$

The question is to find a CFG for this language: $$\{ u v w v^R\ |\ u, v, w \in \{a,b\}^+,\ |u| = |w| = 2\},$$ where $v^R$ denotes the reverse of $v$. I've been trying, but I'm not sure how to have $w$ in between $v$ and $v^R$. Just for the v and…
Herious
  • 157
2
votes
2 answers

Example of a non context-free language whose complement isn't context-free as well

The language $L=\{a^{2^n} \mid n \geq 0\}$ isn't context free (easily proved using the pumping lemma). But what about its complement? It seems to me that it's unlikely for it to be context free, but how would one show it?
daniel.jackson
  • 2,361
2
votes
1 answer

My approach to a CFG

this site has been of great help, and I am certainly indebted to your assistance. I was solving a question, $a^i b^j$ where $0\le i\le j\le 2\cdot i$ And here is my approach: $S\to aSb \;|\; aSbb \;|\;e$ Did I solve the problem? What are usually…
Gaak
  • 221
2
votes
2 answers

Context free grammar construction

My problem with CFG is, I am to generally create ones but once they have requirements such as: $$\{a^m b^n: m\le n\le 2m\}$$ I have no clue where to begin, and how to approach it. I was wondering if you can provide some hints for such daunting…
Gaak
  • 221
2
votes
1 answer

$L_4 = \{x: \#_{1}(x) = 2 \cdot \#_{10}(x) \}$ Find CFG given hints

Attempt: $S \to A_{00}SA_{11}$ $A_{00} \to 0, 0A_{00}, 0A_{10}$ $A_{01} \to A_{00}1, A_{00}A_{11}, A_{01}1, A_{00}1$ $A_{10} \to 1A_{10}, A_{10}0, 1A_{00}$ $A_{11} \to 1, 1A_{11}, 1A_{01}$ Not sure what I'm doing. Any help is appreciated
Tree Garen
  • 709
  • 5
  • 15
2
votes
1 answer

What is the CFG for an arithmetic expression with possible matching nested parentheses?

For example, the CFG can produce: 6+(4-(5)+3) OR (7+7+(1-2)+9) OR -6+(-3+7+(9-1)) I have the following…
Samuel
  • 263
2
votes
2 answers

Prove or disprove (with closure properties or using grammars)

1) Define $L = \{a^i*b^j*c^k*d^m \mid \text{ if } a=1 \text{ then } j=k=m\}$. Is $ L$ a context free language ? 2) If $L$ is a context free language then $\mathrm{Mirror}(L) = \{ww^r \mid w \in L \}$ is also a context free language? 3) If $L$ is a…
user14988
  • 21
2
votes
2 answers

Showing a language is context-free with closures

Let $L_1$ a regular language and $L_2$ a context-free one. I need to show that $$L = \{w \mid w = x_1y_1x_2y_2\dots x_ny_n \mbox{ where } x_1x_2\dots x_n \in L_1 \mbox{ and } y_1y_2\dots y_n \in L_2\}$$ is context-free (or not) ($x_i$ and $y_i$ are…
DanielY
  • 979
2
votes
1 answer

Is language L2 Context free or not?

How this language is Context free? $\mathcal{L2}=\{a^ib^jc^i \;|\;i,j\geq 1\}$ Please explain me.
Sudhir
  • 131
2
votes
1 answer

What is the grammar for the following context-free language $L=\{w||a|>|b|\}$?

I want to find the grammar for the following context-free language: $$L=\{w|\mbox{ the number of $a>$ the number of $b$ }\}$$ I tried the following : \begin{align*} S&\rightarrow a|aK\\ K&\rightarrow\varepsilon |(ab)^*|a^*|bS \end{align*} But it…
Revolucion for Monica
  • 1,511
2
votes
1 answer

What is the grammar for the following context-free language $L={w|w=a^*b^ia^*b^{2i}}$?

I'm new to this website. I want to find the grammar for the following context-free language: $$L={w|w=a^*b^ia^*b^{2i}}$$ I tried \begin{align*} S&\rightarrow aS|\varepsilon S | bKSKb\\ K&\rightarrow\varepsilon |bK \end{align*} I want to know if it…
M.TSHIL
  • 21
  • 3
1
2
3
…
12 13