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
0
votes
0
answers
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 ...
- 21
1
vote
1
answer
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 ...
user1256863
-1
votes
1
answer
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 ...
0
votes
1
answer
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 ...
- 9
0
votes
1
answer
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 ...
- 11
0
votes
1
answer
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 ...
- 3
0
votes
0
answers
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 ...
- 127
1
vote
1
answer
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 ...
- 1,277
0
votes
0
answers
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 ...
- 101
0
votes
0
answers
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, ...
- 43
2
votes
0
answers
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 ...
- 21
0
votes
0
answers
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 ...
- 1,002
0
votes
1
answer
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 ...
- 13
0
votes
0
answers
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-...
- 47
1
vote
1
answer
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 ...
- 11
0
votes
1
answer
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?
- 3
2
votes
1
answer
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 ...
- 121
0
votes
1
answer
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 ...
- 15
-1
votes
1
answer
57
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}” = ...
- 1,104
0
votes
1
answer
54
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$$
$$...
- 17
0
votes
0
answers
72
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
60
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
337
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
46
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
38
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
53
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 = \{ ...
user956293
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 ...
- 63
-1
votes
2
answers
73
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, ...
- 63
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?
- 3
0
votes
1
answer
41
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{...
user956293
0
votes
1
answer
59
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,200
0
votes
0
answers
44
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
42
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$. ...
- 1
0
votes
0
answers
33
views
Reduction of Context Free Grammar
I'm doing some problems about reductions of Context Free Grammar and I've some troubles with one of them. Here is the statement:
I tried using morphisms with other symbols with the objective of make ...
- 33
0
votes
1
answer
104
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.
- 387
0
votes
0
answers
27
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
41
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}
...
- 8,188
2
votes
0
answers
68
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'...
- 33
1
vote
0
answers
67
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
33
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 \...
0
votes
0
answers
32
views
Find a CFG for $a^{2n}b^na^k$ where $n,k \ge 0$
I need to provide a CFG for $L=\{a^{2n}\cdot b^n \cdot a^k | n,k \ge 0\}$ .So I am perplexed on how to account for $a^k$ as $S -> aaSb | \epsilon$ gives me $a^{2n}b^n$ but if I do anything like $S -...
3
votes
1
answer
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$$
...
- 33
0
votes
1
answer
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
1
vote
0
answers
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.
- 13
0
votes
1
answer
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.
- 3,872
0
votes
1
answer
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$, ...
- 401
1
vote
1
answer
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,...
- 2,113
1
vote
1
answer
79
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
0
votes
1
answer
88
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?
- 57