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
0
votes
0 answers

Doubts in CFG Ambigous Grammer and Ambiguous language

I have recently starting studying Theory of computation. I have some basic doubts. Can you please clarify my doubts? Inherently ambiguous CFL means there is no unambiguous grammer(why can'nt we say atleast 1 possible grammer for that CFL are…
Nascimento de Cos
  • 793
0
votes
2 answers

Prove that any string formed from the alphabet {0, 1} that has an equal amount of 0's and 1's can always be written as 0x1y or 1x0y

This has me stumped. How can you prove that for the alphabet $\Sigma = \{0, 1\}$, any string $w \in \Sigma^\star$ with an equal amount of 0's and 1's will always have either the format $0x1y$ or $1x0y$ (where $x$ and $y$ are substrings also $\in…
Qqwy
  • 348
0
votes
0 answers

Is the language for the following grammar is correct? $L= \{a^i b^j c^k d^l : i,j,k,l \geqslant0 \text{ and }i+k=j+l\}$

I tried to solve it like this: \begin{align} A &\to aAd+S+\epsilon \\ S &\to PQR \\ P &\to aPb+\epsilon \\ Q &\to bQc+\epsilon \\ R &\to cRd+\epsilon \end{align}
Arpita Dutta
  • 1
0
votes
0 answers

Algorithm for converting grammar to Chomsky normal form application

I am trying to apply the CNF algorithm to this grammar : $S \to NT $ $N \to aNb | ε$ $T \to bTcc | ε$ Here is what I have done with all the steps,however at the end my answer is way different from the one in the book and I can't seem to find my…
Karmen
  • 1
0
votes
1 answer

Show with closures that L is not context-free

Consider this language: $$ L = \{a^n b^{2n} a^n \mid n \ge 0\}$$ I need to show only with closures that it's not context-free. (Actually, I can show it as I wish, except for the pumping lemma for context-free languages, which we haven't studied…
DanielY
  • 979
0
votes
1 answer

$L = \{ a^jb^mc^m : 0 \le j \le m \}$ prove that it is context free.

Having the following language: $$L = \{ a^jb^mc^m : 0 \le j \le m \}$$ I have to prove that it is context free. I have tried to consider the concatenation of smaller context free languages, to take advantage of the fact that the concatenation of…
JB-Franco
  • 852
0
votes
3 answers

is this language context-free? a tricky one

Is this language context-free? $$L = \{a^nb^nc^{2n} \mid n \ge 0\}$$ It's tricky in my opinion because I know that $a^nb^nc^n$ is not context-free, but can I determine from this that $L$ is not context-free, too? Thanks in advance EDIT: I can use…
DanielY
  • 979
0
votes
2 answers

Language to CFG

I have the following exercise. I have to create a CFG from the following language: M = {a^m b^n| 2m > n > m} Currently I have: S -> aaSbbb A -> aaA B -> bbbB Im not sure if this is correct. Also how do I apply limit so that 2m > n still holds…
BABUSH
  • 1
  • 1
0
votes
1 answer

Is the language context free?

Consider the language $$L=\{0^n w 1^m \mid \text{where}\; w \text{ belongs to } (a+b)^* , n \text{ is number of } a \text{'s in }w, m \text{ is no of } b\text{'s in }w \text{ and }n>m \}$$ I can surely say that this is not a DCFL but I am not sure…
Zephyr
  • 1,163
  • 1
  • 15
  • 30
0
votes
1 answer

Pumping lemma for $L=\{w\in\{a, b, c\}^*:w\text{ has the same number of a, b, and c}\}$

I was shown a way to prove this language was not context free by intersecting it with a regular language, however I can't find a string to pump to show that this language is false directly through the pumping lemma. My original thought was just to…
pajkatt
  • 373
0
votes
1 answer

Find CFG for $L=\{0^i1^j2^k\mid i\ne j\vee j\ne k,\ i,j,k>0\}$

I am trying to find context free grammar for the following language $$L=\{0^i1^j2^k\mid i\ne j\vee j\ne k,\ i,j,k>0\}$$ I tried to write the following rules: \begin{align*}S&\to S_1C\mid S_2C\mid AS_3\mid AS_4 \\ S_1&\to 0A\mid 0S_11 \\ S_2&\to…
Galc127
  • 4,451
0
votes
1 answer

Context Free Diagram for this language

I've searched and searched and can't find a similar CFG. I've got this language: $$L=\{a^nb^mc^rd^t:n+m=r+t\}$$ Basically, I have to have the same amount of $a$'s and $b$'s as I have $c$'s and $d$'s. I've gotten close, but the production rules I've…
Kevin Robles
  • 13
0
votes
2 answers

Show that the CFG with productions S→ a | Sa | bSS | SSb | SbS is ambiguous?

How does one know which string to choose when nothing is given in the question?
Paritosh Potukuchi
  • 1
0
votes
1 answer

Context free grammar for the language {a^{i}b^{j}, j> 2i}

I tried to do it by myself and got this answer but this way of deducing the answer doesn't seem to match anyone's answer on the internet. $$S \rightarrow aSbbB$$ $$B \rightarrow bB|\epsilon$$ Am I missing something?
Paritosh Potukuchi
  • 1
0
votes
0 answers

Translate Grammar to plain english

G ::= S S ::= A M A ::= a E | b A A M ::= S | ϵ E ::= a B | b A | ϵ B ::= b E | a B B where a and b are terminals So I tried to do a derivation for this but I realized there's no point where you're left with just terminal variables? How do describe…
greenteam
  • 333
1 2 3
…
12 13