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

939 questions
Filter by
Sorted by
Tagged with
18 views

### Creating a context free grammar for this language. (Having difficulties keeping track of $3$ parts).

create a context free grammar that creates this language: $\{w_1bw_2bw_3 : w_1,w_2,w_3\in \{a,c\}^* \space\text{and}\space |w_2|+|w_3|<2|w_1|\}$ Usually when I solve context free grammar questions,...
• 2,051
1 vote
38 views

### Is DCFL closed with regular always?

Suppose $L=\{a^mb^n∣m≠n\}∪{(a+b)^∗b(b+a)^*a(a+b)^∗} =\{a^mb^n|m<n\} \cup \{a^mb^n|m>n\} \cup (a+b)^*b(a+b)^*a(a+b)^*$  It is DCFL ∪ Regular, hence it should be DCFL, but not able to design DPDA, ...
• 111
95 views

### Prove that $L\subseteq 0^*$ is context free iff $L$ is regular.

Prove that $L\subseteq 0^*$ is context free if and only if $L$ is regular.
14 views

### How to show $(L^+)^R$ = $(L^R)^+$ [closed]

I wanted to show that $(L^+)^R$ = $(L^R)^+$, I tried the following: $(L^+)^R$ = $L(L^*)^R$. But I don't really know how to continue. Also I'm not quite sure what the $+$ after the $(L^R)$ means. Is it ...
31 views

### How to prove that a language is not context-free using pumping lemma?

How could I realize this using the pumping lemma? What if the pumping part is between b and c or between a and b so that after pumping the word is still in L?
44 views

### Is it possible to create this context-free grammatic?

Is it possible to create this grammatic? $$\left. 0^i 1^j 2^k \right| i + j \ne 2k$$ I try to create this, but I don't understand. I assume that we have to output $k$ characters '2' beforehand. But ...
56 views

### My proof of $\{a^p|p~~\mathbb{is~~prime}\}$ is not a CFL.

I want to show that the language $L=\{a^p~|~p~~\mathbb{is~~prime}\}$ is not a CFL. Assuming towards a contradiction that $L$ is a CFL. Let $p$ be the number from the Pumping lemma for context-free ...
• 656
36 views

### Proof Attempt: non Context free languages and non regular language with some words added stay non regular/context-free.

Background: I was in class and heard this sentence from my professor "Well if you take a non context free language and add $2$ words to it then it will stay non context free". Now I was ...
• 2,051
43 views

### Is there a s-grammar for $L_2=\{a^nb^m, n > m \ge 0\}$?

Peter Linz - An introduction to formal languages and automata (2001) third edition: A context free grammar $G=(V,T,S,P)$ is said to be a simple grammar or s-grammar if all its productions are of the ...
• 619
14 views

### CFG of $L=\{w \in \{a,b\}^* ~~|~~ \#_a(w)\ge \frac{|w|}{2} \}$

I want to find a CFG for the given language: $L=\{w \in \{a,b\}^* ~~|~~ \#_a(w)\ge \frac{|w|}{2} \}$ Is that correct: $$S \to ~~ aSb ~~|~~ bSa ~~|~~ aSbSa ~~|~~ aS ~~|~~ a ~~|~~ \lambda$$ Thanks!
• 656
74 views

### How can I prove that L = {w ∈ {a, b, c, d} ∗ | #a(w) = #b(w) = #c(w) = #d(w)} is not context-free without using the pumping lemma?

I am stuck on this problem, I can prove it using the pumping lemma, but I'm wondering if I can also prove it using closure properties
24 views

### Is this a PDA for balanced parentheses language?

I have got following PDA: $A=(\{p, q\},\{0, 1\},\{Z\},\delta , p, Z)$ $\delta ( p, 0, Z) = \{(p, ZZ)\}$ $\delta ( p, 1, Z) = \{(p, \lambda)\}$ $\delta ( p, \lambda, Z) = \{(q, \lambda)\}$ Assuming ...
• 1
21 views

### What does the ⇒ mean in Context Free Grammer? Also, how do I derive/get the L(CFG) from a CFG?

I'm a bit confused. Does the ⇒ simply denote you going through the CFG step by step ? To use a pretty basic-ish example: sentence ⇒ subject | predicate subject ⇒ article | noun predicate ⇒ verb | ...
• 11
78 views

### On the general relationship between automata, expressions, and grammars

When I took Theory of Computation, the main points of interest were three kinds of automata: finite, pushdown, and Turing, one type of expression: regular expressions which are equivalent to finite ...
44 views

### Convert a CFG to GNF

I have to convert the below grammar to GNF. $S \Rightarrow SA$ $A \Rightarrow aAb|cCc$ $B \Rightarrow D|ba$ $C \Rightarrow dCd| ɛ$ $D \Rightarrow De|Df|cD|c$ I have seen some examples and tutorials on ...
1 vote
32 views

### Solution Verification: Suggest a context-free grammar that creates this language.

Suggest a context-free grammar that creates this language: $L=\{tct^Rcscw | t,s,w\in (a+b)^*, \space\space s \ne w^R\}$ My Solution Approach: We split the language to $S_1$ and $S_2$, where $S_1$ ...
• 2,051
53 views

### Find a CFG for all the binary strings in which the characters in $i$ and $i + 2$ positions are same, and the length of the string is at least 2.

I have homework which is about CFGs, their simplification, and their normalized forms. I have also seen some examples on the internet, but unfortunately, I could not solve the below question. All the ...
57 views

### Writing a grammar that creates a specific language from a given grammar in Chomsky normal form

Given a grammar in Chomsky normal form that creates a language $L$ over alphabet $\Sigma$, that the letter z doesn't belong to $\Sigma$, without the empty string. I need to write a context-free ...
39 views

### Pumping lemma: if you pump to $uv^0wx^0y$, wouldn't $|vx| \ngeq 1$?

For pumping lemma for CFLs, for strings $s$ in $L$, they follow the form $s = uvwxy$ and $|vwx| \leq n$, $|vx| \geq 1$, and $uv^iwx^iy \in L$ for $i \geq 0$. If I want to prove a language is not CFL, ...
• 1,713
1 vote
71 views

• 1,918
1 vote
38 views

1 vote
39 views

### Induction on automaton [closed]

Let an automaton defined by the following transition table: 0 1 $\rightarrow$A A B $\leftarrow$B B A I have this finite automaton, and it recognizes the languages with only an odd number of $1s$ ...
12 views

### Finding S-Attributed Grammar

Finding S-Attributed Grammar Given a grammar: L -> id LT LT -> , L LT -> ε My attempt: L -> LT LT -> id, L, ε From my understanding, an S-attributed grammar is "bottom-up" so ...
28 views

### Proof of context free Language

$$L:=\{w\in\{a, b, c\}^*| ∃ i, j ∈ N :w = a^i⋅b^i⋅c^j ∧ i < j\}$$ I am trying to prove/disprove that this is context free. I was sure this was not context free, since there are 3 pumping operations,...
121 views

### Finding Context Free Grammar for a language

I was trying to find the CFG for the language below. However, I couldn't do that. Can anyone help with this problem? $$\{1^n 0^m 1^k 0^p | n \geq 2, m,k,p \geq 1, n+k = m+p\}$$
• 43
1 vote
37 views

### Find a CFG for all words that can be obtained in the form $a^ib^{i+k}a^k$

Find a CFG for all words that can be obtained in the form of $a^ib^{i+k}a^k$ where $i,k\ge1$. This is what I have so far: $$S\to aXa \\X\to bXB \mid bb$$ I understand that number of b's must be ...
• 13
1 vote
54 views

### Why is {$0^𝑛 1^𝑛 : 𝑛≥0$} context free?

This Language {$0^𝑛 1^𝑛 : 𝑛≥0$} is context-free as per another answer I read on this site. Link: What does it mean to say a language is context-free? For this example take S = $0^p 1^p$ However, if ...
27 views

• 536
31 views

### Converting a CFG to Chomsky Normal Form with 5 steps

I'm learning how to convert from CFG to Chomsky Normal Form and I'm having problems with this exercise Converting a CFG to Chomsky Normal Form  A→BAB|B|ɛ; B→00|ɛ ...
60 views

### Combination of 2 context free grammars

I am required to show that the language $L$ is context-free where $$L = \{q_1q_2 \dotsm q_nt_1t_2 \dotsm t_n \mid q_i \in Q, t_i \in T, n \geq 0 \}$$ where $Q$ and $T$ are context-free languages. I ...
• 36
45 views

### Is $a^n b^n$ context free even if we take strings instead of characters?

Let a and b be 2 strings . Does the set {$a^nb^n$ , $n\geq0$} still form a context free language? Intuitively, I feel that should be the case since in this case I'm just storing strings instead of ...
• 36
809 views

### How to design a regular language that accept all binary string except for string that contains one specific occurrences?

Good day, I come across this question on my textbook and would like to seek some help. In this question, I was asked to design a regular language that accept all binary string except for string that ...
1 vote
Given the following language: $$L = \{b^n \mid \text{n is prime} \}\cup \{b^n \mid \text{n is even}\}$$ Need to proof or disproof whether this language is context-free or not. I know that only ...