Questions tagged [context-free]
Questions about the set of languages (equivalently) described by context-free grammars or accepted by (non-deterministic) pushdown automata.
1,687
questions
0
votes
0
answers
13
views
When finding the CNF of a CFG, in the step where you eliminate unit productions, does order matter?
Suppose a CFG has unit productions A -> B and C -> D among other productions, possibly involving ...
- 315
1
vote
2
answers
80
views
Need to create CFG that requires sum of other letters
I have a homework assignment that requires me to create CFG $G$ for
$$L = \{a^i b^{i+j+k} c^j d^k\}$$
so that it can accept words like ab, aaabbbbd, abbbcd, but it should not accept abba, aabbbbbc, or ...
- 11
2
votes
0
answers
101
views
How to write a grammar with a low-precedence unary postfix operator?
Like this person on Google Groups, I'm trying to understand how to write a grammar involving Wolfram Language's low-precedence unary & operator.
The operator ...
- 121
1
vote
1
answer
616
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 | ...
- 111
0
votes
2
answers
82
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.
- 1
0
votes
0
answers
30
views
First Set for this grammar? Is it Indirect Left-recursive
Given the grammar (Uppercase alphabet is non-terminal, lower-case alphabet is terminal), how to find FIRST set?
A -> mB | CD
B -> CBn | epsilon
C -> pA | epsilon
D -> q
This is NOT a ...
- 1
0
votes
0
answers
49
views
Proving that $L = \{a^n b^m |\: m \:\%\: n = 0 \ \}$ is not context-free
For language $L = \{a^n\, b^m\: |\: m \:\%\: n = 0 \}$, that is, 𝑚 is a multiple of 𝑛.
I'm trying to find a proof that it isn't a context free. I know it isn't regular, but it also doesn't seem to ...
- 1
0
votes
2
answers
677
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 ...
0
votes
1
answer
53
views
How to make LR(1) grammar for sequence that cannot have more "Up" than "Down" for any given prefix?
I am working on a problem that asks me to write an LR(1) grammar that satisfies the following rules:
Consider a robot arm that accepts two commands: $\triangledown$ puts an apple in
the bag and $\...
2
votes
0
answers
136
views
Determining when a substring has a unique parse forest
Given an arbitrary (potentially ambiguous) context free grammar $G: \mathbb{G}$, and string $\alpha: \Sigma^\ast$, is there a decision procedure that returns whether appending and/or prepending ...
- 33
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-...
0
votes
0
answers
59
views
Methods of eliminating ambiguity in CFG
I am looking for all possible ways to find and eliminate ambiguity in CF grammar. Please share your knowledge or opinion (preferably you will indicate the literature so that I can familiarize myself)....
- 1
0
votes
1
answer
49
views
In Context free languages, is it okay to substitute multiple same variables at the same time?
Let's say we have the following context free grammar:
$S \rightarrow a \\ S \rightarrow SS$
And we do the following two "derivations" for the same string:
aaa: $S \rightarrow SS \rightarrow ...
- 305
0
votes
1
answer
47
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 ...
- 337
0
votes
1
answer
31
views
Why $L$ = { $uc^nu$ | $u$ ∈ $P$, $n > 0$ } isn't context-free?
$P$ is the set of all words of even length on {0,1}.
Hi, i tried using pumping lemma to see why $L$ isn't a context-free language, but there's a decomposition where none of all three properties is ...
1
vote
1
answer
26
views
$|v|$ and $|x|$ factorizations (in Pumping lemma for context-free) have the same length?
When i iterate $v$ and $x$ factorizations to see if a word is still in a language $L$, do i have to assume that $|v| = |x|$ always or could happen theirs lengths are different?.
I'm asking because i ...
0
votes
1
answer
49
views
Convert regex for comma separated value to CFG grammar
I have the following regex that I'm trying to convert to a CFG: e|a(,a)* (e representing the empty state). Basically I want to ...
2
votes
1
answer
41
views
Duplicate rules in CFG
Suppose I have the following CFG that I would like to bring to CNF
S -> TA | bA | Ab | b
A -> Aa|a
T -> Ab
Then I have two options to get rid of the ...
- 155
1
vote
0
answers
37
views
Which non regular language meets the requirements for pumping lemma for regular languages?
I heard in my lecture that there are non regular languages which meet the requirements for the pumping lemma for regular languages but I never actually saw one. Does anybody have an example?
0
votes
0
answers
30
views
Are $L' = \{uu| u \in P \} $ and $L" = \{uuu| u \in P \}$ context-free languages?
$P$ is the set of all palindrome words.
I tried using pumping lemma for context-free languages on $L'$. I've distinguished two possible cases:
(Factors = $uvwxyz$)
(Iterating factors = $v$ and $x$)
...
0
votes
1
answer
52
views
Are there any updates to CYK parsing that handles epsilon rules in arbitrary nonterminals?
I am a researcher starting to work on the field of parsing and recognition of languages.
As part of my background research, I am reading up on CYK. I understand that it requires the grammar to be in ...
- 337
0
votes
1
answer
96
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 ...
0
votes
1
answer
297
views
How to use the Pumping Lemma to show that a language is not context free?
I have the following alphabet $\Sigma = \{0,\dots,9\}$ and the following language over $\Sigma \cup \{\#\}$:
$$L=\{\#w \ |\ w \in\Sigma^*,\sum_{i\geq1}w_i\ \text{is prime}\}\\\\$$
This language ...
- 105
0
votes
1
answer
105
views
PushDown automata for a^(n) b^(2n) c^(2n) d^(n)
i got this question in a theory of computation quiz "give pda for a^(n) b^(2n) c^(2n) d^(n)"
i am arguing that there is no pda for that question but our ta says that we can push 5x to the ...
-2
votes
1
answer
43
views
Build a context-free grammar for the language
Build a context-free grammar for the the complementary language of:
$L=\{ww^{R}\,\,|\,\,w\in\{0,1\}^{*}\}$
I think $L^C$ is the set of all strings that are not palindromes,
but I don't know how to ...
- 99
-1
votes
1
answer
47
views
Build a context-free grammar for the language
Build a context-free grammar for the language:
$L=\{\#x\#y\#\,\,;\,\,|x|=|y|\,\,\wedge\,\,x,y\in\{0,1\}^{*}\}$ over $\sum=\{0,1,\#\}$
How can I make sure that |x|=|y|?
- 99
1
vote
1
answer
111
views
Is the equivalence problem of a CFG and a FSM decidable?
I have the following problem:
Given a context-free grammar $\mathcal{G}$ and a finite state automaton $\mathcal{A}$, where both are over the alphabet $\Sigma=\{0, 1\}$. Is it decidable whether $L(\...
- 15
-3
votes
1
answer
40
views
Is a^n , n = 3j+4k , n>=0, a context-free language?
I have no idea how to approach this question... How would I go about proving or disproving this? any explanation is appreciated.
- 1
0
votes
0
answers
34
views
Is a^n b^k , 0 <= n <= k^2, a context-free language?
I don't think it's a CFL, but I'm having a hard time using the pumping lemma to prove this. Is there any way I can use homomorphism? Maybe h(a)= a, h(b) = lambda...
If the pumping lemma is more ...
- 1
-1
votes
1
answer
52
views
How do I show language consisting prime number of 0s or prime number of 1s is not context-free?
The language is: L1 = {w | n0(w) or n1(w) is prime}
n0 means number of 0s and n1 means number of 1s I can show a^n (n is prime) is not context-free. But I can't ...
0
votes
1
answer
133
views
Context Free Grammar Advantages
I am currently learning about context-free grammar, however, I am confused as to why context-free grammar is used over regular languages(Regular expression) and what makes CFG more powerful. Even ...
- 11
0
votes
1
answer
64
views
Why the Following Grammars Are Not in CNF
I am reading the book "Automata, Formal Languages, and Automata" written by Dr. Emre Sermutlu and in page 153, it is stated that the following grammars are not in Chomsky Normal Definition (...
- 143
1
vote
0
answers
131
views
How does ANTLR4 handle optional rules?
Are the following two stat rules equivalant?
stat : 'if' expr 'then' stat ('else' stat)? ;
...
- 9,501
0
votes
1
answer
58
views
Intersection of CFL and DCFL
Is CFL $\cap$ DCFL = CFL, always true?
CFL - Any Context Free Language
DCFL - Any Deterministic Context Free Language
1
vote
1
answer
90
views
Can CYK algorithm be used even if the grammar is ambiguous?
Can CYK algorithm be used for ambiguous context free grammar?
0
votes
2
answers
106
views
Proof: CFG has balanced parentheses
I'm currently enrolled to a CS course about programming languages and we learned about structural induction. In a question from our home assignments we need to proof that the following CFG has ...
0
votes
1
answer
38
views
What context-free grammar recognizes a list of numbers 1 - N in order?
I'm looking for a context-free grammar that recognizes precisely the numbers 1 - N in order:
...
- 401
1
vote
1
answer
104
views
Shuffle of a DCFL and a regular language
This is problem 88 from Miscellaneous exercises of Kozen's "Automata and Computability".
The shuffle $A||B$ of two languages $A$ and $B$ is defined as $\{w \mid w = a_1b_1\ldots a_kb_k,$ ...
- 13
6
votes
1
answer
918
views
Language of ambiguous words
Consider an ambiguous context-free grammar $G$. Define $A(G)$ the set of ambiguous words, meaning:
$$A(G) = \{u\in L(G) \mid u \text{ has at least two derivation trees for }G\}$$
Can we say something ...
- 12.5k
0
votes
1
answer
51
views
Push Down Automata
I am learning about context free languages.
I understand how $\{a^nb^nc^n|n>0\}$ can be shown to be not context free using the pumping lemma for CFL's.
Intuitively however it seems that a pushdown ...
- 1
0
votes
1
answer
29
views
Determining class of language with pumping lemma?
I have the language $L = \{ 0^{2l} 1^m | l,m >= 0 \} \ where \ \Sigma= \{0,1\} $
which I am trying to find the class of language for, e.g. not context-free, context-free, regular.
By this notion I ...
- 3
1
vote
1
answer
783
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 ...
- 11
0
votes
1
answer
36
views
Context Free Language Twist [duplicate]
I am trying to recognize a particular language,
L= {a^n b^k | n<=k<=2n}
and according to me it should not be CFL, as i can see two comparision i.e. firstly number of a is compare to keep count ...
0
votes
1
answer
89
views
0
votes
2
answers
97
views
Context free grammar for $L= \{0^i1^ic0^j1^j | j = i+1 \}$
Description
This is an exercise for Formal Language course, I'm asked to find a grammar for language:
$L = \{ 0^i1^ic0^j1^j | j = i+1 \}$
As an example: 01c0011 can be generated using this language, ...
- 3
0
votes
1
answer
212
views
Find the language generated by the Context Free Grammar
I am trying to find the language generated by this context-free grammar
S → aSb | bbY | Yaa
Y → bY | aY | ε
I understand that one way to solve is this to find set ...
- 111
1
vote
1
answer
66
views
Regular expressions cannot be used to express context free grammars. Is there a similar notation that can?
Regular expressions are a powerful practical tool for string processing. But there are simple examples of useful string processing tasks (like, say, removing brackets from an expression ...
- 141
0
votes
0
answers
53
views
context free grammar for ${\{0^i1^j0^k1^l0^m \mid i, j, k, l, m \ge 0, i \le k\text{ or }j = m\text{ (or both)}\}}$
I'm trying to come up with a context free grammar for the following language: $${\{0^i1^j0^k1^l0^m | i, j, k, l, m \ge 0, i \le k \text{ or } j = m \text{ (or both)}\}}$$
I'm able to come up with ...
0
votes
0
answers
59
views
Context free grammar of $ L=\{a^nb^m, n\neq 2m\} $ [duplicate]
I have to find the context-free grammar of this language:
$ L=\{a^nb^m, n\neq 2m\} $
So I did:
$ S \to a \mid aYb \mid \epsilon$
$Y \to aSb \mid X \mid \epsilon$
$X \to bX \mid \epsilon $
is it ...
- 1
0
votes
1
answer
53
views
Context free language with valid Pumping Lemma use
Is this language context free?
$L = \{a^kb^lb^ka^l \ | \ k,l \in \mathbb{N}\}$
Using Pumping Lemma and $z = a^nb^nb^na^n$ I find it contradicting PL.
If $z = uvwxy$ and $|vwx| \leq n$, follows:
$vwx$...
- 25