# 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.

847 questions
Filter by
Sorted by
Tagged with
26 views

### Converting Context Free Grammar to Greibach Normal Form

I'm having a hard time with this example. In order to convert CFG to GNF I follow these steps required by my professor: Convert grammar to Chomsky NF (remove useless symbols (non-generating, then non-...
19 views

### Is CFL complement PTIME?

Is CFL complement PTIME? If so, why? Im sure it's NPTime because i can verify is some word is (not) in CFL using CYK algorithm. (In polynomial time) But what about PTIME?
26 views

### Is the given Language $L$ regular?

$L = \{ a^nb^m : m + n\text{ is divisible by }3 ; m,n\ge 0\}$. Is this language regular, and if so, what is the regular expression?
14 views

### pumping lemma for context free languages

As part of the homework we were asked a question about context free languages, and the proof is done using the pumping lemma for CFL. (Prove that it is not a CFL, proof by negation.) The question is ...
61 views

### CFL grammer questions

I'm preparing to my test and I have 2 question in past test with no answers. Could you help me? Prove or disprove the following claim. The language $$L=\{a^n\mid n!=k^2, k\ge 0\}$$ is a CFL. I now ...
81 views

### Is this language $L$ context free?

$L$ is a language combined with the symbols $\texttt{a}$, $\texttt{b}$ and $\texttt{c}$ given by: $$L = \{ v\texttt{c}w \mid v, w \in \{ \texttt{a, b} \}^*\text{ and } v \neq w \}.$$ I tried to prove ...
14 views

### Determine if complement of non-regular language is context-free

I'm trying to understand if the complement of non-regular language is context-free. for example: $L=\{ 0^n 1^n │ n\ge0 \}$, I need to prove that the complement of $L$ is regular so $L'$ is context-...
26 views

### Is there a context free grammar that is both in Chomsky Normal Form and ambiguous?

I know that converting an ambiguous context free grammar (CFG) to be in Chomsky Normal Form (CNF) might make it unambiguous, but is it a method that necessarily makes any CFG unambiguous? My knowledge ...
21 views

### If L* is context-free, is L context-free as well?

I know CFL in closed under Closure, but don't know how to prove it back. I try to construct a CFG for L* such as S->ε|AS and say since L* in a context-free language, there must exist a method to ...
126 views

### Pumping Lemma for CF language exercise

I have this language $$B=\{x\in \{a,b,c\}^*:(x\text{ not contains } aabb \text{ or } bbcc \text{ or } aaaa) \land \#(a,x)=\#(b,x)=\#(c,x)\}$$ The notation $\#(s,x)$ indicates the number of ...
19 views

### Is every sentential form also a right-sentential form?

Ullman's Introduction to Automata, Languages and Computing (1979) says 10.6 LR(0) GRAMMARS ... A right-sentential form is a sentential form that can be derived by a rightmost derivation. Is every ...
11 views

### How to characterize the set of grammars which recursive descent parsers can apply to?

How would you characterize the set of grammars which recursive descent parsers can apply to: no left recursion (both immediate and not) left factored no cycle no epsilon rule ... Predicative ...
16 views

### Context free grammar for language $\{ \{a,b\}^*$: where the number of $a$'s is unequal to the number of $b$'s$\}$

I've seen many solutions for when the number of $a$'s and $b$'s ARE equal but how should the grammar be for the time when the numbers are unequal? So far I have this but it can't produce many things ...
44 views

### Formally proving that $\{ L = { {a^i}{b^j}{c^k}, j = \min(i,k), i, k > 0\} }$ is context-free

Please no hints. I need to formally prove that $\{ L = { {a^i}{b^j}{c^k}\mid j = \min(i,k),\: i, k > 0\} }$: At first my idea was to use pumping lemma, so I tried to study where $\\|vwx|\$falls ...
49 views

### Prove that $L=\big\{\langle G\rangle \mid G\text{ is a CFG over }\Sigma=\{0,1\}\text{ and }1^* \cap L(G)\ne\varnothing\big\}$ is decidable.

How to prove that $L = \big\{\langle G\rangle \mid G \text { is a CFG over } \Sigma = \{0,1\} \text { and } 1^* \cap L(G) \ne \varnothing\big\}$ is decidable? I know I am supposed to prove that it is ...
15 views

### What is the minimum and maximum number of productions in Chomsky and Greibach Normal forms?

How many min and max number of productions will be required in Chomsky Normal Form(CNF) and Greibach Normal From(GNF) each if string length = n ? I've heard somewhere that in GNF, minimum and max ...
19 views

### Do CFG' concepts of derivation and derivation tree apply to grammars more general than CFG?

Ullman's Introduction to Automata, Languages and Computation (1979) says that given a CFG $G$, Two strings are related by $\to_G$ exactly when the second is obtained from the first by one application ...
15 views

### Chomsky Normal form for any CFG that doesn't generate ⋋?

Can someone explain me this statement? It is easy to find Chomsky Normal form for any Context Free Grammar that doesn't generate ?
14 views

### Is every production in a CFG an $A$-production?

In Ullman's Introduction to Automata, Languages and Computation (1979): A context-free grammar (CFG or just grammar) is denoted $G = (V, T, P, S)$, where $V$ and $T$ are finite sets of variables and ...
18 views

32 views

### Constructing CFG for even length words with maximum of two 0's

How to I generate a CFG from the language that have even length and have at most two 0’s L3 = {w ∈ {0, 1} ∗ | w is even length, 0<=2 } I feel stuck on meeting the criteria of maximum two 0s My ...
41 views

### Finding Context free grammar from a language

I am trying to construct context-free grammar from the following language accepted by this PDA $L(A)=\{a^n c^m b^{2n} \mid n, m \in {\Bbb N}, m \geqslant 2 \}$ I am particularly stuck on how to ...
60 views

### CF grammar for a Language.

I am trying to formulate a CF grammar for a language of alphabet { a , b, c} with a condition that the number of characters a standing anywhere in the word before this given c larger by 3 than the ...
19 views

### Finding the context free language

I am a self taught software developer and i came to a problem which i can not solve , can you please help me find the context free language of this language? Thank you . Here is the example , i ...
68 views

### If a language is Turing decidable, does that make the sublanguages also Turing decidable [duplicate]

Let $L$ be a language over a finite alphabet $A$. A language $L'$ over the same alphabet $A$ is called a sublanguage of $L$ if $L' \subset L$. Assume that $L$ is Turing-decidable. Does it follow that ...
34 views

### formal languages write context-free grammar

I have been confusing a question for 2 days. I think I solved the question, but I don't know if it's true. Can you help me tell me I did it right or wrong? The question is ; Write a context-free ...
21 views

### How is $\{uv \in \{0,1\}^* | \space|u|=|v| \text{ and } u\neq v \text{ at exactly 2 characters} \}$ not a CFL?

I'm looking at the following language, and it is given to me that it is not a CFL: $$\{uv \in \{0,1\}^* | \space|u|=|v| \text{ and } u\neq v \text{ at exactly 2 characters} \}$$ However, if I ...
140 views

### context free grammar that generates binary all numbers divisible by 3

I'm struggling with the grammar that generates all binary numbers divisible by 3 I know that for a binary number to be divisible by 3 the sum of 1s in even bits mines the sum of 1s in odd bits must be ...
34 views

### Is the language $𝐿=\{𝑎^𝑖.𝑏^𝑗.𝑐^j.𝑑^i:𝑖,𝑗≥0\}$ context free language? [closed]

Is the language $𝐿=\{𝑎^𝑖.𝑏^𝑗.𝑐^j.𝑑^i:𝑖,𝑗≥0\}$ context free language? If yes, what is the context-free grammar?
### Transforming a grammar $G$ to Greibach normal form
$\newcommand{\rewrite}{\longrightarrow} \newcommand{\lang}{\mathcal L} \newcommand{\set}{\left\{ #1 \right\}} \newcommand{\perm}{\left\langle #1 \right\rangle}$ I would like to transform the ...