Questions tagged [context-free]
Questions about the set of languages (equivalently) described by context-free grammars or accepted by (non-deterministic) pushdown automata.
1,681
questions
0
votes
1
answer
130
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 → ...
CommunityBot
- 1
1
vote
1
answer
556
views
CFG for the language {w ∈ {0, 1}∗ : w is a palindrome and |w| is divisible by 3}
The question is the following:
Construct CFG for the L = {w ∈ {0, 1}∗ : w is a palindrome and |w| is divisible by 3}.
I am able to construct CFG for the set of all palindromes as below:
S --> aSa | ...
CommunityBot
- 1
1
vote
3
answers
598
views
Need help understanding what co-recursively enumerable means
Lets say I have a set: $ L = \{\langle G \rangle | L(G) = \Sigma^{\star}\}$ and the question asks if it is co-RE. I know that if something is co-RE, it halts on every input not in L but may or may not ...
CommunityBot
- 1
0
votes
1
answer
105
views
CFG for the given language $L = \{~ a^\ell a^n b^m c^m d^n e^\ell ~|~ \ell,n,m \geq 0 \}$
I am writing this CFG to solve the problem:
$S \to ASBSC$
$A \to aAe ~|~ ε$
$B \to aBd ~|~ ε$
$C \to bcC ~|~ ε$
Is this correct or not?
- 25
0
votes
1
answer
93
views
Intersection of Infinite Regular Language with CFL
Intersection of any finite regular language with anything( CFL or not CFL) will be finite but what about intersection of infinite regular language with CFL or not CFL. Does the resultant will be ...
CommunityBot
- 1
-2
votes
0
answers
36
views
L = {xy : x, y ∈ {a, b} ∗ , |x| = |y| and x ̸= y^R} where y^R is the reverse of y
How can I convert this context free langauge to conext free grammar? Please help I can not solve this problem for days.
L = {xy : x, y ∈ {a, b} ∗ , |x| = |y| and x ̸= y^R} where y^R is the reverse of ...
0
votes
2
answers
651
views
Is the language $L = \{0^i 1^j | i \ne 2j\}$ context free?
I have been trying to find a a CFG for this language generated.
I came to the conclusion that I need three parts
When $i \le j$
When $j < 2j < i$
When $j < i < 2j$
I was able to come up ...
- 28.3k
1
vote
2
answers
364
views
Does there exist an context free language L such that L∩L^R is not context free?
By the closure property of context-free languages, if $L$ is context-free, then $L^R$ (the reverse of $L$) is also context-free, but $L\cap L^R$ might be non-context-free. I tried to come up with an ...
- 29.8k
-3
votes
0
answers
33
views
How do I convert this context free language to context free grammar L1 = {0^i 1^j : i ̸= j, j ̸= 2i}
How do I convert this cfl to cfg L1 = {0^i 1^j : i ̸= j, j ̸= 2i}
2
votes
2
answers
49
views
Derivation trees to show a given grammar is ambiguous
Given the grammar with productions:
\begin{align}
S \rightarrow aSb \mid SS \mid \lambda\\
\end{align}
I would like to show that it is ambiguous. As I understand it, if you can show that some string ...
- 1
-1
votes
0
answers
57
views
Can we give an example Context-Free Language that a DPDA can not recognize
Can we give an example Context-Free Language that a DPDA can not recognize. If we DPDA can not recognize can you explain why?
- 1
0
votes
1
answer
29
views
Proof that $\{0^m 1^n : 0\le m\le n^2\}$ is not a CFL
I am trying to prove by the pumping lemma that $L=\{0^m1^n:0\le m\le n^2\}$ is not a CFL. Here is what I have so far.
Suppose for contradiction that it is a CFL and let $N$ be the pumping length. ...
- 12.5k
0
votes
1
answer
57
views
Is L={0^n 1^n ∣n≥0} context free language?
I looked through many sources which give this as an example for cfl. It also makes sense according to this:
But it fails the pumping lemma test.
Let's take n=5.
According to the Pumping Lemma, we can ...
- 28.2k
0
votes
1
answer
79
views
What could be possible NFA for the RegEx "a?"
I am trying to use the Thompson's method to draw an NFA for a RegEx given by: $(a+b|c?)c$
I am wondering if I should deconstruct the RegEx as -
Concatenation of $a+$, $(b|c?)$ together with $c$ OR
...
CommunityBot
- 1
0
votes
1
answer
238
views
What to do following a reduce in LR(1) parsing?
I am using this standard question from Dragonbook as an example, (the first problem) . I have trouble with what happens in State 4 on LR(1) parsing. Once it is reduced by the rule C->d, now what ...
CommunityBot
- 1
-4
votes
1
answer
26
views
Which one is an LL(2) but not an LL(1)
I'm pretty sure b and d are ll2 and not one but not 100% sure.
(a) S → aaScc | aaBbc | aaBbb | aBb | ac | Ʌ
B → aBb | Ʌ
(b) S → aaScc | aaBbc | aBb | ac | Ʌ
B → aBb | Ʌ
(c) S → aaScc | aaBbc | B | ac |...
- 28.3k
1
vote
1
answer
771
views
Understanding this PDA for non-palindromes over {0,1}
I found this PDA online that accepts all non-palindromes over {0,1}. However, I can't seem to understand how it would accept, say "01011", and not accept "101101". Can someone help ...
CommunityBot
- 1
0
votes
0
answers
46
views
Turing machine for a^n b^m c^n d^m
The state diagram for the initial part of this turing machine given as:
Here, we are basically traversing through the input tape, changing occurence of 'a' to X1, and 'c' to X2. After that we go back ...
- 101
0
votes
1
answer
735
views
How to determine valid handle for given bottom up parser?
I came across following question:
Consider the grammar:
$E → E + n\text{ | }E × n\text{ | }n$
For a sentence n + n × n, the handles in the right-sentential form of the reduction are
(...
CommunityBot
- 1
0
votes
1
answer
37
views
Question about $L$ = { $ww$ | $w$ ∊ $ca^*c$}
I found a grammar for this language.
$S->caZac |cccc $.
$Z->aZa | cc$
But if I try to use pumping lemma for context-free languages on $L$ with the word: $ca^ncca^nc$ I obtain it's not context-...
CommunityBot
- 1
0
votes
0
answers
31
views
Language of words concatenated with themselves
Let $L$ be a regular language.
Is the language $L_2 = \{ ww | w \in L \}$ context-free? Does it have a name?
- 2,184
-1
votes
0
answers
79
views
Convert CFG to CNF
I have been struggling with this conversion problem. Would very much appreciate some verification on this.
Given:
S' -> S $ ($ is a terminal)
S -> a A B | b B A | ε
A -> a | S
B -> b ...
- 1
2
votes
1
answer
151
views
Is $\{a^ib^ja^k \mid j \text{ is odd, then } k=i^2+j ;\ j \text{ is even, then } k =i+j\}$ context-free?
$L=\{a^ib^ja^k \mid j \text{ is odd, then } k=i^2+j
;\ j \text{ is even, then } k =i+j\}$
I tried writing $L$ as the union of the language created with $j$ odd and the one with $j$ even.
When $j$ is ...
CommunityBot
- 1
0
votes
1
answer
39
views
How can I transfer the following language into an context-free grammar?
My problem of understanding is how to create a new a before the b's if you create new c's.
Hopefully someone can help me out.
CommunityBot
- 1
4
votes
1
answer
9k
views
Removing Left Recursion from Context-Free Grammars - Ordering of nonterminals
I have recently implemented the Paull's algorithm for removing left-recursion from context-free grammars:
Assign an ordering $A_1, \dots, A_n$ to the nonterminals of the grammar.
for $i := 1$ to $n$ ...
CommunityBot
- 1
0
votes
1
answer
33
views
An elementary question about grammar
Recently, I am studying grammar in automata. And, I have few information about this subject.
I have a grammar with rules $\{S\to ASA, A\to aA, A\to \epsilon\}$.
Is it true if I say that $S\to aASA$ ...
- 29.8k
-1
votes
1
answer
35
views
Write a CFG for a language of the form L_1 ={a^ib^jc^kd^m|i,j,k>=0, i +j +k> m}
I'm currently having trouble coming with context free grammar to describe this language.
My current intuition is to generate an arbitrary amount of a,b,c's on my string and then whenever the character ...
- 29.8k
0
votes
1
answer
46
views
Generating parse trees when only a recognizer is given
I am trying to understand "On the complexity of general context-free language parsing and recognition" by Walter L. Ruzzo. One of the results from the paper is about generating a parse tree ...
CommunityBot
- 1
0
votes
1
answer
55
views
Let P be the language of palindromes over the alphabet Σ = {0, 1}. and let P‘ be the subset of the palindromes with different numbers of 0s and 1s
Let P be the language of palindromes over the alphabet Σ = {0, 1}. and let P‘ be the subset of the palindromes with different numbers of 0s and 1s. Is P' context-free? I know that for the language of ...
- 29.8k
1
vote
2
answers
199
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 ...
CommunityBot
- 1
1
vote
0
answers
30
views
How need help to specify a grammar for arithmetic expressions
I am trying to come up with a grammar for arithmetic expressions with the following order of operations:
Parentheses
Factorials
Exponents
Functions / unary plus and minus
Juxtaposition (implied ...
- 111
0
votes
1
answer
167
views
How to demonstrate unambiguous CFG and CNF?
I have to show that if G is an unambiguous CFG, the transformed grammar G' in CNF is also unambiguous. But couldn't come up with something concrete. I could only visualize the case where the grammar G ...
CommunityBot
- 1
0
votes
1
answer
104
views
Pumping Lemma for $\mathcal{L} = \{ \omega \omega^R a^{|\omega|} : \omega \in \{a,b\}^* \} $
I have to show that this language is not context free $\mathcal{L} = \{ \omega \omega^R a^{|\omega|} : \omega \in \{a,b\}^* \} $, where the $R$ corresponds to the reverse. For this I will use the ...
CommunityBot
- 1
0
votes
1
answer
79
views
Is $L = \{w w^r w | w \in a(b+c)^*a \}$ a context-free language?
Can't understand how to apply pumping lemma to see if a language is context-free or not.
I tried to verify the context-free's pumping lemma, and the language seems to be not context-free but I can't ...
CommunityBot
- 1
1
vote
1
answer
139
views
Dangling else determinism
The natural grammar for dangling "else" is ambiguous.
But there exists an unambiguous version of the grammar that links the "else" to last uncompleted "if" statement.
Is this version also ...
CommunityBot
- 1
1
vote
2
answers
205
views
Are there any algorithms that decide if a PDA (pushdown automaton) accepts a sentence?
Most computation theory textbooks just mention the equivalence of PDAs and Context Free Grammars. I'm able to construct a PDA from a given CFG, but find it very difficult to write an algo to check if ...
D.W.♦
- 156k
1
vote
2
answers
84
views
Show for every $CFL$ $L$ that's not $REG$ exists $L_1,L_2$ with $L_1$ is $REG$ and $L_1 \subseteq L_2$ and $L_2$ is not $REG$ and $L \subseteq L_2$
i want to show that for all $CFL$ and not $REG$ languages $L \subseteq \{0,1\}^*$
exists $L_1,L_2\subseteq\{0,1\}^*$ with:
$L_1$ is $REG$
$L_2$ is $CFL$ and not $REG$
$L_1 \subseteq L_2 $
$L \...
CommunityBot
- 1
0
votes
2
answers
146
views
Build PDA for a language with unknown input alphabet
$L_1 ,L_2$ are regular language. We form a new language $L_{12}$ as follows:
$$L_{12}=\left \{ w_1\cdot w_2\mid w_1\in L_1\land w_2\in L_2\land |w_1|=|w_2| \right \}$$
In this exercise I am not given ...
CommunityBot
- 1
0
votes
0
answers
41
views
Is $\{ 0^{a}10^{a}1 0^{a}|a \in \mathbb{N}\}$ a context free language?
I was thinking about whether $\{ 0^{a}10^{a}10^{a}|a\in\mathbb{N} \}$ is a context-free language, and I found this post. I am not sure if my understanding is correct or not, but I guess $R = \{ (a,1,a,...
- 101
0
votes
2
answers
78
views
Example 7.1 correctness in Introduction to Automata Theory, Languages, and Computation
The example says that C is unreachable, but there is the production S-> aBC so C is clearly reachable. This is an error right? or am I missing something.
CommunityBot
- 1
1
vote
1
answer
72
views
Is $L=\{1^n2^n3^m : n\neq m\}$ context free?
Is the language $L=\{1^n2^n3^m : n\neq m\}$ context free?
I checked and it satisfies the pumping lemma (Right?). Does it also satisfy Ogden's lemma, or any other test for being non-context free?
- 76
0
votes
1
answer
37
views
Find Grammar for L(G) ={a^i b^j c^k | k = i*j ;i, j ≥ 1}
Find a Grammar G, so that L(G) = {a^i b^j c^k | k = i*j ;i, j ≥ 1}
Hello, I have difficulties solving this. I had a similar exercise, where the k was i+j, which was easier, because the solution was to ...
CommunityBot
- 1
1
vote
1
answer
168
views
How to prove L := { a^n b^n c^m | n,m >= 0 & n != m } is not context-free?
I have following language $L:= \{a^n b^n c^m \mid n \neq m; n,m \ge 0 \}$ and would like to use proof by contradiction by applying Pumping Lemma for CFLs to show that $L$ is not a CFL.
In any case, i ...
- 29.8k
1
vote
1
answer
50
views
Does this really define a 0L-system?
Looking through old exams I found a problem stated as the following:
Define a 0L-system as a 3-tuple $S = (\Sigma, w, h)$ where $\Sigma$ is an alphabet, $h:\Sigma^* \to \Sigma^*$ is a homomorphism ...
CommunityBot
- 1
0
votes
2
answers
5k
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 ...
CommunityBot
- 1
0
votes
1
answer
112
views
prove or give counterexample about regular language
Let $\Sigma = \{a,b\}$, $L_1,L_2\subseteq \Sigma^*$
$L_1 ◃ L_2 = \{w∈ \Sigma^* | \exists v\in L_1, vw \in L_2\}$
For any context-free language $L$, regular language $R$, whether $L \triangleleft R$ ...
CommunityBot
- 1
0
votes
0
answers
25
views
Confused about decomposition in Context Free Pumping lemma
Okay so here's my current solution for the question that asks whether the language is context free:
$$L = { a^nb^{3n}c^n | \, n \geq 0 } $$
Assume by contradiction that L is context-free.
Let p be ...
- 1
12
votes
4
answers
6k
views
Is Python a context-free language?
From Wikipedia: Off-side_rule#Implementation, there is a statement:
...This requires that the lexer hold state, namely the current
indentation level, and thus can detect changes in indentation ...
- 7,768
1
vote
4
answers
13k
views
How to prove {a^(n^2) | n>0} is not context-free?
So I have a language:
$$
L = \{a^{n^2} \mid n > 0\}
$$
I need to prove that this language isn't context-free using the pumping lemma. I have a vague thought process as to how to do the proof but I'...
10
votes
1
answer
451
views
Shift-resolve parsing - questions
I've recently came across a paper describing the parsing technique
mentioned in the title. Unfortunately, the terminology used in said paper
is somewhat beyond my comprehension, so I've been ...
CommunityBot
- 1