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
1 answer

find the grammar for the language that contains all and only the words that have the form: $(a ... b c (b) (c c) b ) (a (c b) c ... a (b) a b)$

Give a context-free grammar for the language,with $\Sigma=\{(,),a,b,c\}$,that contains all and only the words that have the following form: $(a ... b c (b) (c c) b ) (a (c b) c ... a (b) a b)$ ,that is a text with balanced parenthesis,that contains…
evinda
  • 7,823
0
votes
1 answer

How is $L = \{ a^{i}b^{j}c^{k} \space | \space 0 \le i \le j \le k \}$ not a CFL?

The string $a^{i}b^{j}c^{k}$ could be generated by the following grammar: $$ S \rightarrow SSS \space | \space aS \space | \space bS \space | \space cS \space | \space a \space | \space b \space | \space c $$ by the below derivation: $$ S…
Masked Man
  • 233
0
votes
1 answer

syntax analysis of expression!!

I have a question. Given the following grammar: $$S \to ABC$$ $$A \to aA| \varnothing$$ $$B \to bB|a$$ $$C \to bCb|aCb|\varnothing$$ I found that its Chomsky form is: $$S \to AS'|BC|AB|VB|a$$ $$S' \to BC$$ $$A \to UA'|UU$$ $$A' \to AU$$ $$B \to…
evinda
  • 7,823
0
votes
1 answer

Which language is accepted by the grammar

Given the following grammar, I have to find which language is accepted. $$\{x \in \{1,2,3,4\}^{*}: S \to S_{14}, S_{14} \to 1S_{14}4 | S_{24}| S_{13}, S_{24} \to 2S_{24}4 | S_{23}, S_{13} \to 1S_{13}3 | S_{23}, S_{23} \to 2S_{23}3 | \varnothing \}$$…
Mary Star
  • 13,956
0
votes
2 answers

how can I draw the pushdown automaton for a language

How can I draw the pushdown automaton for the language $\{w \in \{a,b,c\}^{*}:w \text{ is of the form } y c y^{R}, y \in \{a,b\}^{*}\}$?
evinda
  • 7,823
0
votes
1 answer

Closure properties-show that language is contextfree

I have a question..Using the closure properties,I have to show that the language $\left \{ w\epsilon \left \{ 0,1 \right \}^{*}:w\neq 0^{m}1^{m},m\geq 0 \right \}$ is contextfree.Could you give me a hint how to start?
evinda
  • 7,823
0
votes
1 answer

Ambiguity of Context Free Grammar

There is a theorem related to CFGs that " There exists no algorithm which can decide whether a grammar is ambiguous or not." I have developed an algorithm which can decide the ambiguity of a cfg. But the proof of the above theorem is based on Post…
user112822
  • 79
  • 1
  • 1
0
votes
1 answer

Prove that $OVERLAP_{CFG}$ is undecidable

Consider the language $OVERLAP_{CFG} = \{\langle G, H \rangle \mid G \text{ and } H \text{ are CFGs, where } L(G) \cap L(H) \neq \emptyset\}.$ I aim to show that $OVERLAP_{CFG}$ is undecidable. We can use the reduction method to $A_{TM}$ but I can't…
guglielmo
  • 31
0
votes
0 answers

Reducing the number of symbols in this string system

This is a bit like Boolean algebra (except it isn't, it is tangle composition - but a lot of main rules agree): | is legit If t is legit, (t) is If t and T are legit, tT is (don't worry, concatenation is associative) (4. If this helps, ((t))=t -…
Hauke Reddmann
  • 735
0
votes
0 answers

superstring(L) = {$xyz$ | $y ∈$ L and $x, z ∈ Σ*$} is a context-free language?

For every language L over the alphabet Σ, let superstring(L) = {$xyz$ | $y ∈$ L and $x, z ∈ Σ*$}. Prove that if L is a context-free language, then superstring(L) is also a context-free language. I know (and able to demonstrate) that context-free…
guglielmo
  • 31
0
votes
2 answers

Prove a CFG is ambiguous

I need to prove this context free grammar ambiguous, I know to prove this I need to find 2 different paths of the same string, but this question has 'begin' and 'end' which I don't know what they mean S -> begin A end A -> A ; A | a | S
Herious
  • 157
0
votes
1 answer

Define a grammar for language $L = \{a^{n}b^{*}c^{2n+1} \}$

could someone please help me define grammar for given language (or help me to improve mine): $L = \{a^{n}b^{*}c^{2n+1} | n >= 1\}$ this is what I have so far, but it is not correct: $$S → aSc$$ $$S → BC$$ $$B → bB$$ $$B → ε$$ $$C → cC$$ $$C → ε$$
No Ziffer
  • 19
0
votes
0 answers

how to find the grammar (production rules) for this?

Let S → ababa | aabaabaa| aaabaaabaaa | aaaabaaaabaaaa | …… find the Production Rules? I've tried like 50 rules, but I can't seem to find the right ones. can I please get a hint on how to start?
Alfa Team
  • 1
0
votes
1 answer

Context free grammar for the same amount of a’s and b’s, with the b’s in the middle

I need to convert the following language to a CFG $$ L = \{\ a^n b^{n+k} a^k \in \{a,b\}^* \ |\ n \ge 0\ ,\ k\ge 0 \} \ . $$ So far I have: $$ \begin{aligned} S &\Rightarrow SASBSA \ ,\\ A &\Rightarrow a\ ,\\ B &\Rightarrow bb|b\…
moonraker
  • 103
0
votes
0 answers

Find a CFG for $a^{2n}b^na^k$ where $n,k \ge 0$

I need to provide a CFG for $L=\{a^{2n}\cdot b^n \cdot a^k | n,k \ge 0\}$ .So I am perplexed on how to account for $a^k$ as $S -> aaSb | \epsilon$ gives me $a^{2n}b^n$ but if I do anything like $S -> aaSbT$ the I start getting garbage…
Oswaldo Mobrey
  • 9
1 2 3
…
12 13