Questions tagged [context-free]
Questions about the set of languages (equivalently) described by context-free grammars or accepted by (non-deterministic) pushdown automata.
1,154
questions
-4
votes
2answers
68 views
What is the language L, generated by the grammar G?
Given the grammar $G = (Ν, Σ, Π, S)$, where $Ν = \{S\}$, $Σ = \{0, 1\}$, $Π = \{S → ε, S → 0, S → 1, S → 0S0, S → 1S1\}$, and $S$ is $S$. What is the language generated by the grammar?
0
votes
1answer
77 views
Find a CFG for $\{a^ib^jc^k \mid i,j,k\ge0 , \text{if } j=1 \text{ then } i=k\}$
I've tried but I can't figure out any solution. Is there any hint for me to solve the question?
1
vote
1answer
40 views
Is this language is Context-free language or not?
Is anybody can help me please to determine is this language is Context-free language or not?
L={wvw | w,v∈{a,b,c}+}
for example:
part of the language: acbac, abcab, bbcbb
not part of the language:...
1
vote
1answer
58 views
How to find First in a left recursive grammar?
One of the basic requirements for a grammar to be LL(1) is : For every pai r of productions A -> X | Y, First(X) and First(Y) should be disjointed.
If a grammar is left-recursive, then the set of ...
3
votes
1answer
51 views
Create a grammar that generate the language a^n . b^m . c^q . d^p such that n + p = q + m
I'm stuck on this question. I'm struggling on how to keep track of the number of a and d I have generated.
The professor hasn't given the correction.
I have seen similar questions but the condition ...
1
vote
1answer
39 views
Is λ allowed in Deterministic CFG?
I have a non-deterministic CFG that says
S-> aS | aB | bB | λ;
B-> bB | λ
And I'm asked to create a deterministic CFG from that. I understand why the given CFG is non-deterministic because it ...
1
vote
1answer
41 views
Whether it's necessary for a grammar to be ambiguous when it is both left recursive and right recursive
I read somewhere that if a grammar is left recursive as well as right recursive, then it is not necessarily ambiguous.
I couldn't make up my mind on this statement. How can a grammar which is both ...
1
vote
0answers
22 views
(Non) Context Free Language…? [duplicate]
I hope you could help me as you have done before (thanks again)
In a previous exam I saw this question; it is asked to identify if the language is Regular, CFL or Non CFL.
In my opinion this ...
0
votes
0answers
138 views
The rightmost derivation is possible with the same rule of leftmost derivation
Can someone please help me in understanding the statement. What does it exactly mean?
What I think it means is that:
the derivation produces by the leftmost derivation is also possible with rightmost ...
0
votes
0answers
55 views
Grammar for context free language
I want to give a grammar for the following language:
$$L = \{x^r \# y |x, y \in \{a, b, c\}^*\\
\text{
and }x\text{ is a contiguous sub-string of }y\}$$
where $x ^ r$ denotes the backward written ...
0
votes
1answer
43 views
Is this language L context-free?
The language
$$L = \{x^r \# y | x, y \in \{a, b, c\}^*\\
\text{
and }x\text{ is a contiguous sub-string of }y\}$$
where $x ^ r$ denotes the backward written word x, is context-free.
Can someone ...
0
votes
0answers
43 views
Prove by Pumping Lemma that Language $L=\{a^ib^kc^k : i\geq k\geq 1\}$ isn't Context-Free
I'm new to this forum. I have some difficulties on using Pumping Lemma to prove non-CF language.
Let $L=\{a^ib^kc^k : i\geq k\geq 1\}$ and the followings are my attempt.
Proof. Suppose by ...
1
vote
1answer
59 views
Does a Context-free language have a grammar that has either 3 or 0 nonterminals on the right hand side?
Is the following true or false? Why?
Let L be a context-free language with $\epsilon\notin$ L. Then there is $\epsilon$-free grammar $G=(V,\Sigma, P,S )$ with $L (G) = L$, so all production rules are ...
2
votes
1answer
48 views
Is this proof for showing that $EQ_{CFG}$ is co-Turing-recognizable incorrect?
I have been searching for proofs that show that $EQ_{CFG}$ is co-Turing-recognizable. When searching for proofs I can only find proofs on the following form:
Construct a TM $M$ which recognizes the ...
3
votes
2answers
38 views
Can the pumping lemma for context free languages be extended to any subword?
It is known that in the case of a Regular Language $L$ , the pumping lemma can be extended to apply to any sufficiently long subword of the language, ie, if $uwv \in L$ and $|w| \ge p$ then we can ...
1
vote
1answer
40 views
Constructing CFG
How to generate CFG for this language?
$ L = \{ w \mid w \in \{ (, [, ], ) \}^* \text{ s.t. } $
In any prefix of $w$, no. of ( is more than no. of ), and
no. of [ is more than no. of ].
$\}$
Thus,...
-1
votes
1answer
50 views
Find the language from a context free grammar
I am having trouble determining the language from a given context free grammar. I've been given a hint that there are 2 parts to the language but can't figure either out.
$$G= (\{S,A,B,C,D,E,Z\},(0,...
0
votes
0answers
44 views
How can I find a language from a given PDA
I have the following PDA:
And a given solution for his languages ${L}_{\mathrm{End}}(M_2)$ and ${L}_{\mathrm{PDA}}(M_2)$ with $ \mathrm{L}_{\mathrm{End}}\left(\mathrm{M}_{2}\right)=\left\{\mathrm{a}^{...
5
votes
1answer
53 views
Mildly context-sensitive grammar
Consider a context-sensitive grammar $G$, such that all the productions of $G$ have the form $A\to \alpha$ or $Ab \to \alpha b$ (in other words, the left context is always empty and the right context ...
1
vote
1answer
56 views
Converting CFG from GNF to CNF
I am working with grammars that need to be in Greibach Normal Form. I want to check whether a grammar recognises a string. In order to perform CYK the grammar would have to be converted into CNF. Is ...
4
votes
2answers
68 views
Does there exist a context-free language $L$ such that $L\cap L^2$ is not context-free?
I can see that $L$ has to be context-free but not regular here as regular languages are closed under concatenation and intersection. But $L\cap L^2$ looks too weird. I couldn't think of any $L$ that ...
0
votes
1answer
57 views
DFA for $L = \{y \in (a+b)^* \mid ||y|_a - |y|_b| \leq 10 \}$
$L = \{y \in (a+b)^* \mid ||y|_a - |y|_b| \leq 10 \}$
Any idea? I have problem with this kind of task.
-1
votes
1answer
64 views
How construct PDA to $L = \{x \in(a,b,c,d)^* \mid -10 \leq ( |x|_a + |x|_b) - ( |x|_c + |x|_d) \leq 10 \}$
$L = \{x \in(a,b,c,d)^* \mid -10 \leq ( |x|_a + |x|_b) - ( |x|_c + |x|_d) \leq 10 \}$
I don't have any idea. Can someone help me.
0
votes
1answer
56 views
Is complement $L = \{ w : |w|_{a} \equiv |w|_{b} \vee |w|_{c} \equiv |w|_{d} \}$ context-free
$L = \{ w : |w|_{a} \equiv |w|_{b} \vee |w|_{c} \equiv |w|_{d} \}$
In my opinion complement of the L language is
$L^{C} = \{ w : |w|_{a} \neq |w|_{b} \wedge |w|_{c} \neq |w|_{d} \}$
I choose to ...
6
votes
3answers
117 views
First half of context-free palindromes
If $L\subseteq\Sigma^*$ is a regular language, then $\text{mir}(L) = \{ww^R \mid w\in L\}$ is context-free. This is a nice exercise.
Question: does the reverse hold? Thus, if $\text{mir}(L)$ is ...
0
votes
1answer
83 views
Prove $ L = \{ww^{R} \in \{a, b\}^{*} : |w|_{a} \equiv |w|_{b} \equiv 0$ $ (mod$ $13) \} $ is regular or context-free or neither
$ L = \{ww^{R} \in \{a, b\}^{*} : |w|_{a} \equiv |w|_{b} \equiv 0$ $ (mod$ $13) \} $
Exercises: If the language L is regular (build a DFA or regular expression)
else if the language L is context-...
1
vote
2answers
112 views
Is the language of words that contain a square regular or context-free? [duplicate]
$ L = \{w \in\{a,b\}^{*} : \exists_{x,y,z} , w=xyyz \wedge y \neq \epsilon \}$
I have a problem with this exercise. I need to determine if this language is regular, context-free or not both and ...
1
vote
1answer
81 views
Is Language $ L = \{ww^{R} \in \{a,b,c\}^{*} : |w|_{a} \not\equiv |w|_{b} $ and $ |w|_{b} \not\equiv |w|_{c} \} $ context free?
$ L = \{ww^{R} \in \{a,b,c\}^{*} : |w|_{a} \not\equiv |w|_{b} $ and $ |w|_{b} \not\equiv |w|_{c} \} $
I would use the Ogden pumping lemma. Assumption $n < m$ where $n$ is a number from lemma. My ...
3
votes
2answers
159 views
How to prove the equivalence of two CFG for balanced parentheses?
Given two CFGs for balanced parentheses.
$S \rightarrow SS \mid (S) \mid \epsilon$
$S \rightarrow S(S)S \mid \epsilon$
How do I show that they are equivalent?
I have been able to show $ L(2) \...
1
vote
1answer
32 views
NPDA transitions to different states by taking same input and popping same top element of a stack
Suppose i have some NPDA and there is some transition functions defined as:
$\delta(q_{1},a,A) = (q_{2}, A)$
$\delta(q_{1},a,A) = (q_{3}, Z)$
Is it allowed?
I understand, that since the NPDA is ...
2
votes
0answers
744 views
Turing machine VS Push Down Automaton in CFL
I want to ask that between turing machine and pushdown automaton: which abstract machine can handle context-free language (CFL) in a more efficient way, and why?
I know that a pushdown automaton can ...
2
votes
2answers
50 views
Is this counting language context free?
Let $\Sigma = \left\{ 0,\,1,\,2\right\}$. I want to look at the following language: $L=\left\{ xyz \, | \, |x|_0 + |z|_0 = |x|_2 +|z|_2 \wedge y \in \left\{ 1 \right\} ^{*} \right\}$.
I would like ...
1
vote
1answer
45 views
How to prove that if $L, G$ are regular languages then $\{w\in L|\exists x\in G: |x|=2\cdot |w|\}$ is a context-free language?
Prove that if $L, G$ are regular languages over $\{a,b,c\}$ then $H=\{w\in L|\exists x\in G: |x|=2\cdot |w|\}$ is a context-free language?
I think this could be a good exercise and the conditions are ...
1
vote
1answer
48 views
Grammar of words with exactly $k$ prefixes in another grammar
Given a context-free grammar $G$, how can one systematically construct a grammar $G_k$ such that
$$ L(G_k) = \{w \in \Sigma^* : |\text{Pref}(w) \cap L(G)| = k\} $$
where $\text{Pref}(w)$ is the set ...
0
votes
1answer
72 views
Does left factoring CFG make it unambiguous?
I came across following problem:
If the CFG is left factored then it must be Unambiguous and Not left Recursive.
TRUE/FALSE?
I have many thoughts about this. But I feel they are somewhat ...
1
vote
1answer
40 views
Is this context-free grammar correct for this regular expression?
I have created a context-free grammar
$$
\begin{align*}
&S \to S_1 \mid S_2 \\
&S_1 \to aS_3bS_4 \mid \epsilon \\
&S_2 \to bS_4 \\
&S_3 \to aS_3 \mid \epsilon \\
&S_4 \to aS_4 \...
2
votes
2answers
42 views
Decidability of $SEQ_{CFG} = \{⟨G,H⟩ \mid \text{$G,H$ are CFGs and $L(G) ⊆ L(H)$}\}$
How can I prove that $SEQ_{CFG} = \{⟨G,H⟩ \mid \text{$G,H$ are CFGs and $L(G) ⊆ L(H)$}\}$ is decidable ?
I know that $EQ_{CFG} = \{⟨G, H⟩ \mid \text{$G,H$ are CFGs and $L(G) = L(H)$}\}$ is not.
1
vote
1answer
35 views
is $0^x1^y$ context-free?
given that L is regular, does the following make a context-free language?:
i) $\{0^x1^y \mid 0^{x+y} \in L\}$
ii) $\{0^x1^y \mid 0^{x-y} \in L\}$
since L is regular, i presumed that i) can be put ...
2
votes
0answers
38 views
Is the language $L$ of coded CFG's Turing decidable?
Consider the following language
$L$ = {$<G><w>$ | $G$ is a CFG and $w\in L(G)$}
Now, I wish to prove that $L$ is Turing decidable. My gut tells me to construct a Turing machine that ...
1
vote
2answers
50 views
What's the right way to think about a CFG symbol with an infinite null derivation?
I'm curious about the right way to characterize symbol $A$ in a CFG like this one:
$$
\begin{align*}
A &\to A B\\
A &\to x\\
B &\to y\\
B &\to \varepsilon
\end{align*}
$$
$B$ is ...
2
votes
1answer
21 views
If you have a smallest grammar approximation, do you immediately have a CFG inference algorithm?
The smallest grammar problem is to find a single-string CFG. So given a finite list of language samples, known to all lie in some CFG, can we, using the smallest grammars (approximated) of each ...
1
vote
3answers
61 views
Give a Context Free Language, is the complement of this language always recursive(REC)?
I have seen some people make an argument that given the fact that Context Free Languages are proper subset of REC which is closed under complementation thus complement of a CFL must be in REC. I ...
-1
votes
2answers
409 views
How to construct Context Free Grammar of words with equal number of 0's and 1's [duplicate]
i am trying to find a cfg for this cfl
L = $\{ w \mid w \text{ has an equal number of 0's and 1's} \}$
is there a way to count the number of 0's or 1's in the string?
0
votes
0answers
41 views
Get grammar from his LALR(1) parsing table
I have a problem with this exercise. This is the LALR(1) parsing table for the grammar G. How can i get the productions of G?
Thanks :)
0
votes
1answer
46 views
SLR(1) Table construction, FIRST and FOLLOWS
when constructing the SLR(1) table for some grammar I need to compute the FOLLOW set for all terminals in order to decide where and when to reduce.
Do I compute theme for the augmented grammar or ...
1
vote
1answer
49 views
Is the following Grammar LL(1)
I was given the following grammar
$S \rightarrow S ( S ) S\mid \epsilon$
First I was asked to eliminate left recursion, yielding me the following :
$S \rightarrow S' $
$S' \rightarrow (S)...
0
votes
0answers
21 views
Are there any formal grammars describing the set of all directed graphs?
Let GRAPHS be the set of all directed graphs.
Is there a set of strings STRYNGS such that there exists a bijection ...
1
vote
1answer
41 views
Can You List the Names of Some Algorithms For Determining the Intersection of Two Context Free Grammars?
Suppose we have two sets of strings XS and YS such that set XS is described by grammar GX and YS is described by grammar GY.
We want an algorithm which accepts GX and Gy as inputs. The algorithm will ...
1
vote
1answer
113 views
Can Non-Linear Grammars generate Regular Language?
I stumbled upon the following non-linear grammar
$$S \to AB$$
$$A\to aaA\mid \epsilon$$
$$B \to Bb\mid \epsilon$$
and the language generated by this non-linear grammar is {a^2nb^m : n ≥ 0, m ≥ 0} ...
0
votes
0answers
30 views
How a regular language , context free language and context sensitive grammar are used in compilers to shape up the languge? [duplicate]
I know that regular language can be used for pattern matching , context free language is used for syntax matching and context sensitive for semantic or meaning of the sentence . But i have found it ...
