Questions tagged [context-free]
Questions about the set of languages (equivalently) described by context-free grammars or accepted by (non-deterministic) pushdown automata.
202
questions with no upvoted or accepted answers
0
votes
0answers
57 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
0answers
66 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 ...
0
votes
0answers
174 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}^{...
0
votes
0answers
50 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
0answers
22 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 ...
0
votes
0answers
41 views
Prove this Context-Free Grammar is Ambiguous
so I have a problem on one of my computational structures final reviews, and I cannot seem to figure it out. It's been driving me crazy, so I would like to post it here for some insight.
Prove that ...
0
votes
0answers
163 views
When proof by induction on length string is not possible?
I found out an exercise where you have to prove the correctness of the following CFG:
Let $L=\{ 0^i 1^j|2i \leq j \leq 3i \}\:$ and
$\: G: S\rightarrow 0S11 | 0S111| \epsilon$
claim: Every string $w ...
0
votes
0answers
37 views
Prove the language L of all palindromes over {0,1} is in NP
Wouldn't this language be in P, since it is a context free language. And every context free language is a member of P? Or would it be otherwise?
0
votes
0answers
103 views
Is $\{ a^i b^j c^k : i + 1000\ < j + 100 < k \}$ context-free?
I have this language:
$$ L = \{ a^i b^j c^k : i + 1000\ < j + 100 < k \}, $$
and what I believe is that we can't prove with the Pumping Lemma that it is not context-free, because we would ...
0
votes
0answers
152 views
Are there any context-free languages that are not regular but can be generated using a right-linear or left-linear grammar?
I understand that every regular language can be generated using either a right-linear or left-linear grammar, however, does that go the other direction? In other words, do there exist any context-free ...
0
votes
0answers
39 views
Computing the shortest path in a labyrinth
I'm currently trying to map how to make a good algorithm that won't have issues to find the shortest path. The labyrinth consists of an X and Y dimensions as input; However, the labyrinth will ...
0
votes
0answers
109 views
Polynomial time verifier for $\overline { EQ_{CFG}}$
How to find, or prove impossible, apolynomial time verifier for $\overline { EQ_{CFG}}$?
$\overline { EQ_{CFG}}$ means all pairs G and H, which are CFGs such that L(G) is not equal to L(H)
0
votes
0answers
457 views
Deciding whether a context-free grammar's language is empty
Consider the formal problem:
Given a context-free grammar $G$, is the language $L(G)$ empty?
Can we determine if the problem is recursively enumerable, recursive, in NP, or in P? Can the entire ...
0
votes
0answers
275 views
Proving infinity of CFL with pumping lemma
Given a CFG G in Chomsky Normal Form with n variables. Prove that
$|L(G)| = \infty \iff \exists w \in L(G)$ such that $2^n<|w|\le2^{n+1}$
Now, proving left to right I've encountered a problem.
...
0
votes
0answers
186 views
How to show that a language is strictly context sensitive
During a class, we was asked how to prove that a language L is strictly context-sensitive. In particular, we have to prove that
$L = \{a^nb^nc^n \mid n > 0\}$
Could you help me to find the ...
0
votes
1answer
531 views
LL1 parsing algorithm for strings generated by a given grammar
How to describe a $\operatorname{LL(1)}$ parsing algorithm for strings generated by a given grammar?
I have to design a parser for a specific grammar.
Let $G$ be the grammar described as:
$$S \...
0
votes
0answers
24 views
Operation on languages results in CFL
For every two languages $L_{1}$ and $L_{2}$ over the alphabet $\{ a,b,c,d \}$, we define the language
$$L_{1} \operatorname{op} L_{2} = \{ \alpha\beta \mid \text{$\alpha \in L_{1}$ and $\beta \in L_{...
0
votes
0answers
49 views
Interpreting the way we choose partitions in the pumping lemma for CFLs
This question is referring to the Pumping Lemma for CFLs, namely:
If $L$ is a CFL, there is a pumping length $p$ such that any string $z \in L$ of length $\geq p$ can be written as $z = uxwyz$, ...
0
votes
0answers
95 views
Doubt regarding Chomsky hierarchy
I know that intersection of CFL and regular language is CFL and hence CFL is closed if one of the languages is regular. One of the most common examples to show this is regular language being $p^*q^*$ ...
0
votes
0answers
140 views
Is this grammar in Chomsky Normal Form?
This was the initial CFG (starting symbol is I):
I → aAB
A → BAb | ε | B
B → a | b | CD
C → ba
D → DD
And this its CNF:
...
0
votes
0answers
340 views
CFL Intersection with Regular Language prove
how can i prove the following statement :
1- $L_1\subseteq\Sigma^*$ is CFL and $L_2\subseteq\Sigma^*$ is regular Language, then $L_1$\ $L_2$ is CFL .
so i want to know what is the method to prove it ...
0
votes
0answers
55 views
Is this grammar L4 ambiguous?
S-> AAB|ABA|BAA|epsilon
A->aS
B->bS
this is a grammar of the language L4 = {w ∈ Σ*: #a(w) = 2#b(w)} over Σ = {a, b}
Does the following examples shows that the L4 is ambiguous?
S->AAB->aSAB->aAB-...
0
votes
0answers
960 views
Can any left recursive grammar be converted into equivalent right recursive grammar and vice versa
I know how to convert any Left Linear Grammar (LLG) to Right Linear Grammar (RLG) and vice versa. This can be done as follows:
Reverse "LLG for L" to get "RLG for LR" by changing A → Ba to A → aB
...
0
votes
2answers
3k views
Removing epsilon transition from context-free grammar
I have the following context-free grammar from which I have to remove epsilon transitions:
$S \to 0A0|0$
$A \to BC|2| CCC$
$B \to 1C | 3D | \epsilon$
$C \to AA3 | \epsilon$
$D \to AAB | 2$
By ...
0
votes
0answers
70 views
How can I build this automaton?
The automaton has to recognize the language $(a^n)(b^m)$ so the number of $b$s is at least the number of $a$s and at most twice that number.
The only thing I have achieved is to get an automaton that ...
0
votes
0answers
31 views
CFG notation meaning in making LL parse table
I have problem of interpreting Context-free grammar notation in making LL(1) parse table.
To make LL(1) parse table. Two rules are shown below:
If A -> α is a production choice, and there is a ...
0
votes
0answers
53 views
Stuck on Converting to Chomsky Normal Form,
I am supposed to be changing this to Chomsky Normal Form and then to Greibach form, but I am still having a few difficulties changing it to the first form.
Here is the language:
S → AA|SBBa|b
A → ...
0
votes
0answers
554 views
Converting a CFG with epsilons into a DPDA
I have a CFG:
S -> $T$
T -> T+T|T-T|T/T|(T)|CX|I
X -> XX |C|N|_|@
C -> a|b|c|....|z|A|B|C|...|Z|_
N -> 0|1|2|....|9
I -> NI|N
Here @ means epsilon.
The above is a valid arithmetic expression ...
0
votes
0answers
158 views
Can two distinct strings create the same parse tree for a given grammar?
More specifically: for any arbitrary CFG, is there guaranteed to exist two distinct strings such that a leftmost parse of both strings creates the same parse tree? If not, does there exist any CFG ...
0
votes
0answers
68 views
How to see if P is decidable semi-decidable, undecidable?
I've been trying to figure out a practice exam question, about if a given $P$.
$P$ is the characteristics of recursive enumerable set given as:
$$P(A) = \begin{cases} ⊤ &if &|A| ≤ 100 \\
...
0
votes
0answers
31 views
Lossless Condensing, Modification, and Decondensing
Given a string $\alpha$ that is derived from context-free grammar $G$, what is an algorithm $f$ such that there exists a string $\beta$ (derived from an unrestricted grammar) where
$f(\alpha)=\beta$,
...
0
votes
0answers
58 views
Pumping Lemma to prove that L is not context free
I have the language and I want to prove that is not context-free.
So I started like this:
is variable.
Choose w =
Case 1:
vxy has no c. Choose i = 2
has more a than c or more b than c.
Case 2:
...
0
votes
0answers
612 views
Describe the language generated by a given context free grammar
I had an exercise: Describe the language generated by the following given context free grammar and prove it by induction.
$$\begin{align}
S &\to SA \mid \epsilon \\
A &\to aS \mid bA \...
0
votes
0answers
436 views
Ogden’s lemma on CFG
I'm trying to understand Ogden's lemma, and I know there are 4 cases, but in the next example I can only find 3:
Assume A = {$0^n1^m0^k$ | k = $max${n, m}} is CF:
Choose z = $0^k1^k0^k ∈ A$, z = ...
0
votes
0answers
61 views
Can we say we reduced a rule if we reduced an equivalent set of smaller rules?
I have constructed an SLR(1) parsing table with the following rules.
S -> S + S + S (rule 1)
S -> S + S (rule 2)
S -> y
Is reducing rule 2, then shifting + and y, then again rule 2, equivalent to ...
0
votes
0answers
70 views
Designing CFG for sequences of words of which two arbitrary ones are reversals
Let $L$ = {$x_1\#x_2\#...\#x_k$ : $k\;\ge\;1$, each $x_i\;\in\;\{0,1\}^*$ and $\exists i,j$ such that $i < j$ and $x_i$ = $x^R_J$}. For example, $001001\#0010\#100100\#00001$ is in $L$ because $...
0
votes
0answers
148 views
Reduction CVP to CFG problem
I want to show that non-emptiness of context free language is P-complete. So, I am trying to reduce CVP to this problem by generating grammar from circuit. I consider all type of gates in circuit and ...
0
votes
2answers
69 views
Determine if the language of words with same number of 1's and 2's is context-free or not
$$L_2=\{w \in \{0,1,2\}^* : \text{$w$ has the same number of $1$'s and $2$'s}\}$$
I have tried creating PDA to determine if this was context-free or not. It seems like it would be because whenever a 1 ...
0
votes
1answer
64 views
Design a CFG that generates the language { x in {a,b}* | the length of x is odd and its middle symbol is a b }
I am trying to design a context-free grammar that generates the language { x in {a,b}* | the length of x is odd and its middle symbol is a b }.
This is really confusing me, I'm having trouble with ...
-1
votes
1answer
41 views
Transform grammar to Chomsky Normal Form
Question:
S → abSab | baSba | TT
T → aTa| bTb | ε
My answer:
Eliminate ε rules:
S-> abSab | baSba | TT | T
T-> aTa | bTb | aa | bb
Correct answer:
S → abSab | baSba | TT | abab | baba | T
T → ...
-1
votes
1answer
28 views
How to simplify context free grammar?
How to simplify this context-free grammar into a similar one with no unit productions and no useless symbols?
$$
S \to ABA \\ A \to aAA \mid aBC \mid bB \\ B \to A \mid bB \mid Cb \\ C \to CC \mid cC
...
-1
votes
2answers
116 views
CFG for language of words with odd many $a$ and exactly two $c$
I am trying to construct a context-free grammar for the language
$$
L = \{ w \in \{a,b,c\} \mid w \text{ contains an odd amount of } a \text{ and there are exactly two } c \}.
$$
I am currently stuck ...
-1
votes
1answer
48 views
Set-theoretic difference of two languages in CFL - REG
Let $L_1,L_2\in$ CFL $-$ REG, with $L_1\subset L_2$. Which of the following always holds?
$L_1-L_2\in$ CFL $-$ REG and $L_1-L_2\in$ REG.
$L_1-L_2\in$ REG and $L_2-L_1\in$ CFL $-$ REG.
$L_1-L_2\in$ ...
-1
votes
1answer
121 views
Convert CFG to CNF Arithmatic Expression
Convert CFG to CNF
The Grammar
E→E+T
E→T
T→T*F
T→F
F→(E)
F→x
Step 1
Assign variables to terminals
A→ +
B→ *
C→(
D→ )
F→x
...
-1
votes
1answer
318 views
Constructing PDA to accept language { 0^i 1^j 2^k | i = 2j or i = k, where i,j,k >= 1 }
$L = \{ 0^i 1^j 2^k \mid i = 2j \text{ or } i = k, \text{ where } i,j,k \geq 1 \}$
I have trouble about this PDA. Anybody can help me about draw this PDA?
-1
votes
1answer
69 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.
-1
votes
1answer
3k views
Describing language generated by grammar
S -> aSb | A | B
A -> aS | a
B -> Sb | b
is this the language generated by this CFG? Or am I missing something?
-1
votes
1answer
996 views
Can we remove unit productions First Before removing Null productions?
My professor have asked me strange question , about converting from Context free grammar to chomsky normal form , Can we remove unit productions first from CFG if possible , before removing null ...
-1
votes
1answer
2k views
Determining whether a context-free language (CFL) described by a given grammar is regular (RL)
In my homework we're given the following problem:
Determine whether the context-free language described by the following grammar is regular, showing all the reasoning steps:
S -> T T | U
T -> 0 T | ...
-3
votes
1answer
96 views
PDA for parentheses language
Construct a PDA for the language described by the following CFG:
$$ S \to [S] \mid \{S\} \mid \Lambda $$
How can I develop a pushdown automaton for this language?
