Skip to main content

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.

Filter by
Sorted by
Tagged with
-2 votes
0 answers
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?
pro yell's user avatar
-1 votes
0 answers
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-...
Polymor's user avatar
1 vote
0 answers
31 views

Prove that $\{a^nb^nc^m\mid n \leq m\}$ is not context-free, using only closure properties

We can use the pumping lemma to prove that $\{a^nb^nc^m \mid n \leq m\}$ is not a context-free language. It turns out that the proof is very similar to the proof for the more famous $\{a^nb^nc^n \mid ...
hugomg's user avatar
  • 333
0 votes
0 answers
8 views

Size of the pusdown stack of NPDA

Assume that a (nondeterministic) pushdown automaton $A$ is given. Given a word $w \in L(A)$, one would like to know how a derivation of $w$ in $A$ might look like. One way to formalise this question ...
lolicomu's user avatar
0 votes
0 answers
26 views

If L is accepted by some deterministic PDA then L has the prefix property.

The question is from Ullaman and Hopcroft Automata theory book. A Language is said to have prefix property if for all words in L, no proper prefix of any of those words exist in L. Prove that if L is ...
harshchy2210's user avatar
0 votes
0 answers
22 views

Undecidability of CFG subtraction under a co-finiteness assumption

Fix a finite alphabet $\Sigma$ for the entire discussion. There is a rather obvious proof that the difference of two context-free grammars $A$ and $B$ (compute the language $L(A) - L(B)$) is not ...
V0ldek's user avatar
  • 101
1 vote
0 answers
48 views

PREFIX-FREE = {$\langle G\rangle$ | G is a CFG where L(G) is prefix-free} is undecidable by reduction to A_{TM}?

Let PREFIX-FREE = {$\langle G\rangle$ | G is a CFG where L(G) is prefix-free}. Prove PREFIX-FREE is undecidable. I've seen several solutions to PREFIX-FREE by reduction to PCP (here). In my course we'...
guglielmo's user avatar
1 vote
0 answers
35 views

$\sum=\{0, 1, \#\}$ $C=\{x\#x^R\#x\# | x \in \{0, 1\}^*\}$ Show C̄ is CFL

From my Automata class $\sum=\{0, 1, \#\}$ $C=\{x\#x^R\#x\# | x \in \{0, 1\}^*\}$ Show C̄ is CFL I want to use pumping lemma for CFL but I can’t understand which type of language is the complement of ...
guglielmo's user avatar
0 votes
0 answers
37 views

$G = \{V, T, S, P\}$, $T = \{0, 1, 2\}$, find production rules P to generate $\{0^n 1^n 2^n | n ∈ ℤ, n ≥ 0\}$

Given $V = \{S, 0, 1, 2,$ any additional nonterminals needed$\}$, $T = \{0, 1, 2\}$, $S$ as the start symbol, list production rules $P$ that can be used to generate strings of the form $\{0^n 1^n 2^n |...
Josh's user avatar
  • 467
-1 votes
1 answer
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 ...
Ethan Powers's user avatar
1 vote
1 answer
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 ...
guglielmo's user avatar
0 votes
0 answers
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, ...
Hauke Reddmann's user avatar
0 votes
0 answers
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 ...
guglielmo's user avatar
1 vote
1 answer
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 ...
user avatar
-1 votes
1 answer
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 ...
Michael kane's user avatar
0 votes
1 answer
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 ...
AmandaF's user avatar
0 votes
1 answer
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 ...
Webber's user avatar
  • 11
0 votes
1 answer
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 ...
jaklois's user avatar
0 votes
0 answers
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 ...
codeing_monkey's user avatar
1 vote
1 answer
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 ...
ghc1997's user avatar
  • 1,641
0 votes
0 answers
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 ...
zegulas's user avatar
  • 101
0 votes
0 answers
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, ...
FallInClouds's user avatar
2 votes
0 answers
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 ...
Nati's user avatar
  • 21
0 votes
1 answer
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 ...
user1179819's user avatar
1 vote
1 answer
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 ...
Nixa's user avatar
  • 11
0 votes
1 answer
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?
MNSAR's user avatar
  • 5
3 votes
1 answer
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 ...
MrHug's user avatar
  • 131
0 votes
1 answer
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 ...
PK96's user avatar
  • 15
-1 votes
1 answer
60 views

How might we formally define the concatenation of two strings?

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}” = ...
Toothpick Anemone's user avatar
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$$ $$...
No Ziffer's user avatar
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?
Alfa Team's user avatar
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=...
Storm Anderson's user avatar
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. ...
James 's user avatar
  • 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 ...
mdirfan's user avatar
  • 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.
mdirfan's user avatar
  • 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 = \{ ...
user avatar
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 ...
Renee Ofadu's user avatar
-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, ...
Renee Ofadu's user avatar
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?
davis29's user avatar
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{...
user avatar
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 ...
Jagerber48's user avatar
  • 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 \...
JohnGam's user avatar
  • 331
0 votes
0 answers
48 views

Let L CFL. Prove or disprove $B(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$. ...
Yuval's user avatar
  • 1
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 ...
moonraker's user avatar
  • 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.
DanielG's user avatar
  • 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 ...
Sam Kiloz's user avatar
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} ...
ploosu2's user avatar
  • 9,763
2 votes
0 answers
70 views

Prove $NOTCONTEXTFREE_{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'...
Prboetic's user avatar
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 ...
Reza's user avatar
  • 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 \...
Black_catto's user avatar

1
2 3 4 5
20