Questions tagged [context-free]
Questions about the set of languages (equivalently) described by context-free grammars or accepted by (non-deterministic) pushdown automata.
1,718
questions
0
votes
0
answers
128
views
Why is DCFL not closed under kleene star? [duplicate]
I honestly haven't an idea how to proof that eventhough I can understand the background, could someone help me?
30
votes
4
answers
3k
views
What's really meant by context-free in the term context-free grammar?
I have been studying compilers for a while, and I have been searching what's meant by "context" in grammar and what it means for grammar to be "context-free", but with no result.
So can anyone help ...
- 411
3
votes
1
answer
445
views
Is $L=\{a^ib^jc^k : i\leq j\leq k\}$ context-free?
I have an exam and in preparation I found this language. We are supposed to determine where in Chomsky hierarchy it stands. The language is $L=\{a^ib^jc^k : i\leq j\leq k\}$. I can easily build a ...
- 31
0
votes
0
answers
1k
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
...
- 1,743
1
vote
1
answer
312
views
how to create tokens from CFG
i have a context free grammar
i want to create a tokens from the language
is there any techniques to do that ?
for example , this CFG from Prof.Alex Aiken notes :
...
- 11
0
votes
2
answers
6k
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 ...
- 179
0
votes
0
answers
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 ...
- 1
2
votes
2
answers
784
views
How these two Turing machine problems are different in terms of their decidability?
I was referring to slide 4 of this, which states following:
It is decidable whether a given CFG accepts a non-empty language?
Then I was reading Intro to Automata theory book by Ullman et al. It ...
- 1,743
1
vote
1
answer
653
views
Context-free Language - Pumping Lemma? [closed]
im having some problems when it comes to Pumping Lemma of Context-free Language ... this is the Language :
$$L = \{a^n b^n c^m | n\ge 0 , 0 \le m \le 2n \}$$
Here is my attemp to prove that the ...
- 19
0
votes
0
answers
32
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 ...
- 235
1
vote
2
answers
91
views
Is it possible to eliminate the unit rules in this?
S -> aA | bC | CC | a | b | C
A -> B
B -> S
C -> A | S
It looks like its going to loop so it would be endless replacing the unit rule....
- 13
1
vote
1
answer
1k
views
Left quotient of a regular language
I have this problem, and I don't really understand how am I supposed to do this. Could someone please help me with this? I know what left quotient is. I also know about regular, irregular languages. ...
- 11
0
votes
3
answers
2k
views
Is it possible to prove Language L context-free? [duplicate]
Give a question:
Language L= {a^n b^(n+m) a^m}, where both n and m are >=0. Is L context-free or not.
If the answer is yes, can I use the following PDA to prove it?
Since {a^n b^(n+m) a^m}={a^n b^n ...
3
votes
1
answer
749
views
Eliminate left recursion from grammar
Consider the following grammar:
$$
A\to Ba|Aa|c \\
B\to Bb|Ab|d
$$
How do I convert this grammar to be LL(1) by eliminating direct and indirect left recursion?
I have tried applying the ...
1
vote
1
answer
419
views
Implement Context-Free Grammar for $L=\{a^n b^m \mid n \neq 2m\}$
I am trying to implement a context-free grammar for $L=\{a^n b^m \mid n \neq 2m\}$.
I have a difficulty trying to implement it because I don't know how to ensure that $n \neq 2m$.
I can easily ...
- 113
4
votes
1
answer
99
views
Why does this grammar derive into $\beta \alpha ^*$ instead of $\alpha ^* \beta$?
In this video clip the teacher presents a grammar $A \rightarrow A \alpha | \beta$ and after providing the parse tree explains that the regular expression for the language generated is represented as $...
- 495
3
votes
1
answer
3k
views
PDA for { xy : |x| = |y|, x ≠ y} from its grammar, and intuition behind it
I know the grammar for the language $\{ xy : |x| = |y|, x ≠ y \}$ if $\Sigma=\{a,b\}$:
$$
\begin{align*}
&S→AB∣BA \\
&A→a∣aAa∣aAb∣bAa∣bAb \\
&B→b∣aBa∣aBb∣bBa∣bBb
\end{align*}
$$
I ...
1
vote
1
answer
2k
views
CFG to generate $L = \{a^{2n}b^n\} \bigcup \{a^mb^{2m}\}$
I've been struggling to find the grammar to generate the language
$$L = \{a^{2n}b^n : n \text{ is natural}\} \cup \{a^mb^{2m} : m \text{ is natural}\}.$$
I've considered
$$S \to aS|Sb|ab,$$
which ...
- 211
2
votes
4
answers
1k
views
How to prove that Ambiguity is still present in Resolved Production of Dangling Else Problem?
$\textbf{stmt} \to$ $ \textbf{if} $expr$ \textbf{then}$ stmt
$\mid $ $\textbf{if}$ expr $ \textbf{then}$ stmt$ \textbf{else}$ stmt
$\mid \textbf{...
- 348
0
votes
2
answers
94
views
Context free grammar issue at pda
I'm studying for my computing languages and I have some problem on getting the production rules from a push down automata.
The automaton accepts all strings over alphabet $\{e,k,q,y\}$ of the form $w\...
- 1
1
vote
0
answers
328
views
Given a DFA $A$ and a CFG $G$, decide whether $L(G) ⊆ L(A)$
Propose a reasonably efficient algorithm to decide, given a DFA $A$ and a CFG $G$, whether $L(G) ⊆ L(A)$.
I think that I have to prove it by computing the intersection of both (DFA,CFG), and then ...
- 11
2
votes
1
answer
492
views
Is there an algorithm for converting a CFG in Greibach Normal Form into a CFG in strong GNF?
A CFG is in strong GNF when all rewrite rules are in the following form:
$A \rightarrow aA_1...A_n$
where $n \leq 2$.
- 23
1
vote
1
answer
99
views
How do you read this context-free language?
say you want to make a Pushdown Automaton to recognize this language.
What exactly does the +1 mean? I see in the example it just pushes an a to the stack before arriving at an acceptance state but I ...
- 125
2
votes
0
answers
409
views
Is the problem that intersection of two cfl is a cfl or not undecidable?
I am trying to use the computation histories argument to fit this. But I am unable to find this as yet.
- 121
1
vote
1
answer
179
views
Noncontext free for quotient
Have such exercise:
Let $L_1=\{a^{2n}b^n|n\geq1\}^*$
and $L_2=\{b^na^n|n\geq 1\}^*b$
Prove, that $L_1, L_2$ are context free, while quotient $L_1/L_2$ is not context-free.
(This is home exercise, ...
- 195
2
votes
1
answer
66
views
Decidability algorithm, whether substring belongs to L
It isn't very hard to decide if word belongs to language L. CYK algorithm should do here.
Occured thought, can CYK be modified to detect if all words of language L contain some specific subword?
- 195
2
votes
1
answer
1k
views
PDA and CFG of language of regular expressions
I am stuck on a problem involving PDA's and CFG's. The problem is as stated:
Give a CFG and a PDA for the language of regular expressions over the
alphabet $\{a, b, c\}$. Give the formal tuple ...
- 21
4
votes
1
answer
7k
views
Does transforming a CFG to Chomsky normal form make it unambiguous?
Does transforming a CFG to Chomsky normal form make it unambiguous?
And if not, is there a technique to convert a CFG G to an equivalent CFG G', so that G' is both unambiguous and LL(1)?
- 103
1
vote
1
answer
1k
views
Deriving epsilon with a context free grammar with epsilon rules
The below problem is from my Formal Languages class. The professor suggested drawing derivation trees for the language until we reach epsilon in all the leaves, and that it should begin to look like a ...
- 13
0
votes
0
answers
127
views
Showing $L=\{a^ib^jc^k: i,j,k \text{ not all equal}\}$ is a CFL a lemma [duplicate]
In their answer, Janoma proves that $\{a^ib^jc^k:i\neq j,j\neq k,i\neq k\}$ is not context-free using Ogden's lemma, but I haven't learned about Ogden's lemma yet. I wanted to know whether Ogden's ...
- 31
4
votes
1
answer
2k
views
Complement of CFL is Recursive
If CFL are not closed under complementation, it means that if a language '$L$' is CFL then its compliment $L^C$ is not CFL. Then how can we discuss about $L^C$ being recursive?
My doubt arose because ...
- 75
4
votes
1
answer
957
views
Finding the language of a context-free grammar?
Given following question:
Let $G$ be a context-free grammar, $G=(V, \Sigma, R, S)$, that has start
variable $S$, set of variables $V = \{S\}$, set of terminals $\Sigma = \{0, 1\}$, and set of rules $...
- 143
0
votes
2
answers
474
views
Intersection with a finite set
If we have a language $F$ and a regular language $D$ (a finite set) then can we say anything about the intersection of $D$ and $F$? Will the intersection of the languages be finite or regular?
This ...
0
votes
2
answers
926
views
How to construct CFG for language
We have alphabet $\Sigma = \{ { a, b} \} $.
How to construct CFG for language $\Sigma^{\ast} - \{a^{n}b^{n} | n \ge 0 \}$.
I suggest that is very easy, but I can't invent. I know PDA for this ...
- 125
2
votes
1
answer
192
views
Is $L / R$ context free?
I was reviewing the post If $L$ is context-free and $R$ is regular, then $L / R$ is context-free?
I completely understand why $L/R$ is context free.
I just tried a different approach, which is not ...
- 462
-2
votes
1
answer
482
views
How to prove that the class of non-context-free languages isn't closed under intersection?
I am not sure how to approach this. L1 and L2 are using the same alphabet.
- 103
1
vote
1
answer
638
views
Proving a language is not context free using the Pumping Lemma
To prove that $L=\{0^m1^n|n \text{ divides } m,\text{ } m,n\gt0\}$ is not a CFG, I applied the pumping lemma. I chose $w=0^{21p}1^{7p}$ for the pumping constant p. By the pumping lemma, $w=xyuvz, |yuv|...
- 309
9
votes
1
answer
834
views
How powerful are CFGs that allow an infinite number of rules?
I was wondering recently what would happen if we'd allow context-free grammars to have an infinite number of rules. Clearly, if we'd allow arbitrary such infinite sets of rules, every language $L$ ...
- 401
2
votes
1
answer
413
views
How to apply the pumping lemma for CFGs to languages that contain the empty string
The pumping lemma states that if we can split a string w (taken from a context-free language L) as uvxyz with conditions |vy|>=1 |vxy|<=p |w|>=p for some p then $uv^ixy^iz$ is in L for any i.
...
- 309
4
votes
0
answers
123
views
Unambiguous context-free language that can't be parsed in linear time by backtracking recursive descent?
Is there a context-free language that can be expressed with an unambiguous grammar but can't be expressed with a grammar that would result in linear-time backtracking recursive descent parsing?
The ...
- 141
0
votes
1
answer
938
views
Can a queue automaton recognize palindromes?
Consider the language of even-length palindromes $L = \{ WW^R \mid W \in \{0,1\}^* \}$. This language is surely context free and I need an NPDA to recognize it.
But, what if we replace the stack with ...
- 462
0
votes
0
answers
33
views
How to design context-free grammars generating the languages with twice as many a’s as b’s? [duplicate]
The problem is designing context-free grammars generating the following languages.
The set of strings over the alphabet Σ = {a, b} with twice as many a’s as b’s.
I found a solution but I don't know ...
- 1
4
votes
0
answers
90
views
Can we define CFL without grammars or automata?
The set of regular languages $R$ over an alphabet $\Sigma$ can be defined as the smallest set satisfying these 5 axioms:
Empty language: $\{\} \in R$
Singleton languages: $\forall a \in \Sigma : \{a\}...
- 416
0
votes
0
answers
91
views
Proving that $L = \{a^m b^n | m \% n = 0 \}$ is not context-free [duplicate]
For language $L = \{a^m\, b^n\: |\: m \:\%\: n = 0 \}$, that is, $m$ is a multiple of $n$, 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 ...
- 179
1
vote
1
answer
169
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 → ...
- 11
6
votes
1
answer
1k
views
Are LR(k) languages and DCFLs equivalent?
In the familiar book of Theory of Computation by M. Sipser, the author proved that for endmarked context-free languages, the set of languages having a LR(k) grammar for a predefined $k \in \mathbb{N}$ ...
- 173
3
votes
2
answers
1k
views
Pascal FOR loop with context free gramar
In Pascal For-do loops, there is a rule stating that one cannot modify the counter variable inside the body of the loop.
To exemplify the rule, take the following Pascal ...
- 333
0
votes
0
answers
1k
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 ...
- 101
0
votes
1
answer
1k
views
Showing that u#v with u a substring of v is not context-free
I need to find whether this language is context-free or not:
{u#v | u,v belong to {a,b,c}* and u is a substring of v}, over alphabet {a,b,c,#}
I suspect that it'...
- 133
2
votes
0
answers
84
views
Correct bracketing check with rotate operation on position i
Given sequence (length $N$) of brackets like $($ and $)$. The task is to implement data structure which supports following operations:
Check whether the sequence is correctly bracketed
Rotate bracket ...
- 49