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

974 questions
Filter by
Sorted by
Tagged with
14 views

### 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 ...
1 vote
216 views

### Proving that a language whose strings have prime length is not context-free

Language is defined as: $L = \{a \space | \space a ∈ \{0,1\}^*\ ∧ \space len(a) \text{ is a prime number}\}$ How to prove that this language is not context-free? By far I was trying to prove it using ... 55 views

### How to show that the language $L = \{a^n , n \geq 10000 \text{ and$n$is prime number}\}$ is not context-free using closure property? [closed]

I proved $L' = \{a^n \mid n \text{ is a prime number}\}$ is not context-free language using the pumping lemma. But I couldn't derive that $L$ is not a context-free language by using closure properties ...
46 views

### Concatenation of languages - Basics

Just trying to understand a homework problem in my theory of computation class: $L_1 = (a^nb^n: n > 0)$ and $L_2 = (c^n: n > 0)$ List the concatenation of $L_1L_2$ where $n = 2$. I can find lots ...
170 views

### Is $M(L)=\left\{w \in L \mid \forall v \in \Sigma^+,vw \notin L\right\}$context-free?

$L$ is a context-free language. We define $M\left(L\right)=\left\{w \in L \mid \forall v \in \Sigma^+,vw \notin L\right\}$ . It seems like $M\left(L\right)$ is the set of strings in $L$ which are not ...
42 views

### I am not sure some notations' usage in the formal language and context free grammar

$L = \{x\#w\mid w^R\text{ is a substring of }x\text{ for }x, w \in \{0,1\}^*\}$, where $w^R$ is denoted the reverse of string $w$ I am not sure # means any valid ...
56 views

### CFG for $L = \{w_1w_2 \cdots w_{2n} \mid n > 0, w_i \in \{a, b\}, 1 \leq i \leq 2n, w_j = b, w_{n + j} = a \ \exists j, 1 \leq j \leq n\}$

I think this is somehow related to the language describing all strings not of the form $ww, w \in \{a, b\}^*$, but I am still not quite sure how. Of course, I have done some thinking and it is evident ...
1 vote
45 views

### Suppose we have unambiguous context-free language, how can we calculate the number of words that can be represented by $n$ terminals?

I am new to formal language theory, apology if this question seems obvious. Here are some definitions from formal language theory: Definition. Let $\mathcal{V}$ be a set of variables (usually denoted ...
28 views

### regex for exactly n possible values which are unique

I want to write a regular expression in my python code, but I think this is more of a mathematical challenge. So my requirement is, suppose I want to create $3$ unique coupon codes, I can write a ...
23 views

### an unclear definition about the types of phrase-structure grammars

I am reading the book "Discrete Mathematics and Its Applications" written by Kenneth Rosen. I've encountered some troubles. When it introduced the type-2 of phrase-structure grammar to me, ...
50 views

### How do I prove that $L = \{a^{i}b^{j}a^{k} | i ≠ j, j ≠ k, k ≠ i ; i, j,k > 0\}$ is not context free?

It's not an assignment question, but I'm trying to prove that $L$ is not context free. $$L = \{a^i b^j a^k \mid i \neq j, j \neq k, k \neq i; i, j, k > 0\}$$ Edit: Thanks for helping me with ...
38 views

### Creating "Zigzag" context-free grammar of $2$ languages with the same letters

Given are $2$ right-linear grammars, forming $L_1$ and $L_2$. The alphabet $T$ is the same for both languages, and $\epsilon$ (empty word) doesn't belong to any of the languages. What is an example of ...
59 views

### Is the following language is regular, context free, and/or decidable?

Given a language determine if it is regular, context free, and/or decidable. No proof needed, but an explanation would be appreciated. A = {a^n b^(2n+6) | n >= 0} My first guess is no its ...
30 views

### Using CFL pumping lemma to show that a language is not context free

consider the language: $$L=\left\{ w*a^n:w\in\left\{0,1 \right\}^*\text{ is the binary representation of the number }n\right\}$$ over the alphabet $\Sigma=\left\{0,1,*,a \right\}$. Is $L$ a context-...
1 vote
90 views

### How can I determine the language from a DFA?

I was given three DFAs to solve. I understand the first one is a*. I think the second one would be b*(a+)*. I cannot figure out what the third one would be, it seems like there are too many different ...
27 views

### Context-free language as regular expression

I want to ask a short question. Can a regular expression expresses a context-free language that is not a regular language?
208 views

### Is L = { words such that the maximum number of as following a b is equal to the maximum number of bs following an a} context-free?

Consider the language $L = \{w \in \Sigma^* \mid$ the maximum number of a's following a b is equal to the maximum number of b's following an a$\}$ over the alphabet $\Sigma = \{a,b\}$. So for example ...
246 views

### Construct Context-Free Grammar for $\{a^ib^jc^kd^l : i,j,k,l\geq1\:\land\: i+j=k+l\}$

One of the tasks on my exam was to construct a context-free grammar for the language: $$L = \{a^ib^jc^kd^l : i,j,k,l\geq1\:\land\: i+j=k+l\}$$ I have no clue how to construct such a grammar, could ...
57 views

56 views

### Non-ambiguous CFG for an expression

I was practicing for an exam of CFG and I'm struggling with this CFG: $L =\{a^ib^jc^k | j \le i+k\}$ I tried this CFG but is ambiguous: $$S\to AXC$$ $$A\to aA|\lambda$$ $$C\to cC|\lambda$$ $$X\to YZ$$ ...
51 views

### Is the following grammar a CFG?

Language $L$ is defined over symbols $a,b,\#$ $$L=\{x\#y\mid x,y∈\{a,b\}^*, x\ne y, \lvert x\rvert=\lvert y\rvert\}$$ Is the above language context free? Though both conditions separately are context ...
1 vote
48 views

### Is this correctly CFG for this language?

$$L = \{ a^{2n}w \mid |w| = n\},\ \Sigma=\{ a,b \}$$ My CFG: $$S \to \epsilon\mid aaST \\ T\to a \mid b$$ My lecturer wrote this is wrong because $w$ but I don't understand why.
33 views

### $LR(k)$ grammar and handles

I would like to understand in the snippet below why $\gamma\to aa$ has both handles $(A\to a,1)$ and $(A\to a,2)$. The definition of a handle is on the top of the snippet.
82 views

### Prove a subset of a regular language is regular, context-free but not regular or not context free [closed]

I've been tasked with solving this problem, but I'm not sure where to begin: Let $L$ be a context-free language. $L'$ contains all the words that belong to $L$ which can't be defined as $z=uvwxy$, ...
1 vote
52 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,...
1 vote
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, ...