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

982 questions
Filter by
Sorted by
Tagged with
31 views

### Prove that $A=\{a^nb^nc^md^m | \geq 0\}$ Is that grammar ambiguous or not? [closed]

Give a context-free grammar that generates the language $A=\{a^nb^nc^md^m | \geq 0\}$ Is that grammar ambiguous? Why or why not?
19 views

### L = { a^n b^m : n != m } - Matrix, Time varying, ordered and programming grammar

I would like help to prepare a thesis that will include: The language chosen, its description, its classification in Chomsky's hierarchy, Matrix grammar generating the language chosen in point 1. Time-...
1 vote
31 views

• 467
30 views

### How do I create a pushdown automata or context-free grammar for this language?

I have a final exam tomorrow, and in preparation, and one of the practice problems is to create a pushdown automaton for this language. My professor has said that it IS context-free, but I can't seem ...
1 vote
113 views

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

### 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, ...
24 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
354 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 ...
66 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 ...
58 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 ...
195 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 ...
• 11
46 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 ...
67 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
54 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 ...
• 1,641
105 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 ...
• 101
34 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, ...
63 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 ...
• 21
97 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 ...
1 vote
134 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 ...
• 11
41 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?
355 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 ...
• 131
610 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 ...
• 15
Below we offer some definitions of string. How would you mathematically define the concatenation of strings? The $\mathtt{HELLO\ WORLD}$ Example $“\mathtt{HELLO}” + “\mathtt{\ }” + \mathtt{WORLD}” = ... • 1,104 0 votes 1 answer 70 views ### 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$$ $$... 0 votes 0 answers 91 views ### 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? 0 votes 0 answers 106 views ### Use the pumping lemma to show that following language is not context-free I was wondering if someone can help explain this question. I've been stuck on it for a while and having a hard time with it. Use the pumping lemma to show that following language is not context-free L=... 1 vote 2 answers 567 views ### How to generate a context free grammar for the language a^i b^j c^k where i+j>k? How to generate a context free grammar for the language a^i b^j c^k where i+j>k? My initial thought was to find the CFG for i+j=k, and then go from there but I've been unable to adapt it. ... • 19 1 vote 1 answer 52 views ### Constructing context-free grammar Construct a context-free grammar generating:$$\{w\# wR \# | w \text{ is a string of one or more 0s and 1s, and a } \# \text{ is between w and its reverse, and a } \# \text{ is at the end}\}The ... • 37 0 votes 0 answers 59 views ### What is the language generated by this grammar? S → 0A | 1B | ɛ | 0 A → 0A | 0S | 1B B → 1B | 1 | 0 I've tried to find some specific properties of some of the generated words, but I've failed. • 37 0 votes 2 answers 75 views ### can the union of regular languages be non-Context-Free I came across the following statement which is supposedly true: There exists an infinite set of regular languages, such that their union is not a CFL it is explained this way: we'll define L_k = \{ ... 0 votes 0 answers 53 views ### Proving Language is Non Regular With Pumping Lemma [duplicate] I have the formal language Z over the alphabet Q \{a, b, c\} and it is generated by the context-free grammar whose non-terminals are S, A, and B, the start symbol is S, production rules are ... -1 votes 2 answers 80 views ### Proving Language is Non Regular Using Pumping Lemma I am working on a question where I have the formal language Z over the alphabet Q {a, b, c} and it is generated by the context-free grammar whose non-terminals are S, A, and B, the start symbol is S, ... 0 votes 1 answer 29 views ### Regular expression extraction from alphabet I have this Alphabet Σ = {k,l} so I do not understand how I can find the words equal bigger than 3 ≤3 in L ((k|l)l*), should I use the words with 3 letters always starting with k or somthing else? 0 votes 1 answer 47 views ### determining CFL for the complement of a language I need to determine whether L is CF \begin{align} \ L = \{a^nb^kc^n | n,k≥0\}^c \end{align} I think L can be represented by the following union: \begin{align}\ L=L_1\cup\ L_2 \end{... 0 votes 1 answer 74 views ### What type of Tree/Graph/Multigraph is a syntax parse tree? Consider a string ((A\lor B)\lor A) We can make an (informally defined) parse tree for this expression whose nodes are subformulas. The root node would be the full formula (A \lor B) \lor A which ... • 1,461 0 votes 0 answers 47 views ### Which language will be generated by the following grammar? So i have G = (V,\sum, S, P) $$while$$ V = {S, A, B}  \sum = {a,b,c}$$and for P:$$ P:= \begin{cases} S \rightarrow & cA\ | \ bB, \\ A \rightarrow & c, \\ B \... • 331 0 votes 0 answers 48 views ### Let L CFL. Prove or disproveB(L) = \{w : w \in L, |w|>10 \} $is CFL I'm struggling with proving or disproving this question. I didn't find any counterexamples, so I tend to think that I need to prove it.$L$is$CFL$, so exist$CFG$,$G=(V,Σ,R,S)$that accepts$L. ... 0 votes 1 answer 160 views ### 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 ... • 103 -1 votes 1 answer 48 views ### Describe the language of S\to0S0\,\,|\,\,1S0\,\,|\,\,\varepsilon [closed] Question Describe the language of S\to0S0\,\,|\,\,1S0\,\,|\,\,\varepsilon. L=\{\Sigma^{n}0^{n}\,\,|\,\,n\geq0\}, but I'm not sure that's an accurate answer. • 397 0 votes 0 answers 44 views ### How to derive a language when there is an unreachable non-terminal symbol? I have this formally defined grammar :\begin{array}{rl}G=\langle&\{S,B,C\},\\&\{a,b,c\},\\&\{S\to CSB\mid CSa\mid a,B\to b\mid\epsilon,C\to c\},\\&S\rangle\end{array}$$I know how ... 2 votes 0 answers 42 views ### Unambiguous grammar for the language S\to A|B, A\to B1|1B, B\to A0|0A|0 I have the following context free grammar$$ \begin{aligned} S &\to A \space | \space B \\ A &\to B1 \space | \space 1B \\ B &\to A0 \space | \space 0A \space | \space 0 \\ \end{aligned} ... • 9,763 2 votes 0 answers 70 views ### ProveNOTCONTEXTFREE_{TM}$is not recursively enumerable?$NOTCONTEXTFREE_{TM}$= {$\langle M \rangle$, M is a turing machine and the language of M is not context-free}. I'm trying to prove the language$NOTCONTEXTFREE_{TM}$is not recursively enumerable. I'... • 33 1 vote 0 answers 73 views ### Questions on Chomsky Normal Form Violations My Professor says I got this problem wrong but I do not see how so. Note that for the problem we do not need to make sure the final answer is in CNF, we are only told to fix one of the violations we ... • 11 0 votes 0 answers 40 views ### Making a CFG for$a^{i}b^{j}c^{k}$such that$i+j=k+3, i,j\geq1\$
I have the language $$L=\{a^{i}b^{j}c^{k} \mid i+j= k+3, i,j\geq1\}$$however I am struggling to convert it to a CFG. I ended up with this grammar: \begin{align} S &\rightarrow aSc \mid aBAc \...