Questions tagged [context-free]

Questions about the set of languages (equivalently) described by context-free grammars or accepted by (non-deterministic) pushdown automata.

Filter by
Sorted by
Tagged with
5
votes
2answers
767 views

Do NPDA work in parallel?

Assume my language is $$ L= ww^{r}\ $$ Now when we use NPDA for this,we will guess middle every time. It may be actual middle or it may not, so a new branch is created every time as I have a choice ...
4
votes
1answer
3k views

Union of a Deterministic Context-free language and a Regular Language is a Deterministic Context-free Language

In formal language theory, deterministic context-free languages (DCFL) are a proper subset of context-free languages. They are the context-free languages that can be accepted by a deterministic ...
3
votes
2answers
257 views

Figuring out the language of a non-linear CFG

I have the CFG G with the following production rules: $$ S \to aSaS \mid b $$ Is it possible to find $L(G)$? I have no idea how describe it by any pattern. I use grammophone to check example words, ...
3
votes
1answer
366 views

Inducing a context free grammar [closed]

I have a file containing a subset of possible strings from a context free language. I am looking for a mechanism to induce the grammar from this information. Is that possible?
3
votes
2answers
527 views

How to check for ambiguous grammar if you don't know the string

Let's say I have a CFG grammar $G$ which describes some rules for language generation. How can you tell that grammar can generate ambiguous results for a string if you don't know that string? I know ...
3
votes
2answers
2k views

Why DCFL is not closed under kleene star?

I have read somewhere that DCFL is not closed under kleene star. but I haven't found any example
2
votes
1answer
311 views

Is vwwx regular language?

I think I understand pumping lemma for regular and context free languages, but there is this one, which I have no idea if it is regular or context free or not context free. $L = \{vwwx : v,w,x \in \{...
2
votes
1answer
2k views

Is $L= \{ a^ib^j \mid j\neq i \ and \ j\neq2i \ \} $ context free?

$L = \{ a^ib^j \mid j\neq i \ and \ j\neq2i \ \} $ Is this language a context free language? If yes give a PDA. If no, give a proof. The pumping lemma for context free languages doesn't seem to work ...
1
vote
2answers
3k views

CFG for $\{a^ib^jc^k \mid i \neq j+k\}$

I am trying to design a context-free grammar for the language $L = \{a^ib^jc^k \mid i\neq j+k\}$ over the alphabet $\Sigma = \{a,b,c\}$. I know that I can split this up into the union of two cfg's $...
-1
votes
1answer
2k views

CFG for the language “number of a's = number of b's + 2”

How can I construct a context-free grammar for the following language? $$ L = \{ w \in \{a,b\}^* : \#_a(w) = \#_b(w) + 2 \}. $$ Please help me out in this. I am not sure how to approach this ...
11
votes
1answer
3k views

Is an infinite union of context-free languages always context-free?

Let $L_1$, $L_2$, $L_3$, $\dots$ be an infinite sequence of context-free languages, each of which is defined over a common alphabet $Σ$. Let $L$ be the infinite union of $L_1$, $L_2$, $L_3$, $\dots $; i....
6
votes
4answers
390 views

Why does $A(L)= \{ w_1w_2: |w_1|=|w_2|$ and $w_1, w_2^R \in L \}$ generate a context free language for regular $L$?

How can I prove that the language that the operator $A$ defines for regular language $L$ is a context free language. $A(L)= \{ w_1w_2: |w_1|=|w_2|$ and $w_1, w_2^R \in L \}$, where $x^R$ is the ...
5
votes
2answers
353 views

Why is the following language not context-free?

$L = \{a^n b^m | m \not= n^2 \}$ I guess I need to use Pumping Lemma for CFL in order to prove this. But I'm stuck. Assuming that $ a^n b^m = uvxyz$, we know that $v$ or $y$ can not have both $a$ ...
4
votes
2answers
7k views

Give CFG and PDA for the words that start and end with the same symbol

I need to give a PDA and CFG for a language that contains all binary strings that start and end with the same symbol. I've created the CFG with no problem, but I'm stuck with the PDA and don't quite ...
4
votes
3answers
186 views

Language of the graph of an affine function

Write $\bar n$ for the decimal expansion of $n$ (with no leading 0). Let : be a symbol distinct from any digit. Let $a$ and $b$ ...
4
votes
3answers
243 views

Designing a CFG that produces as many c's as the difference of numbers of a's and b's

The question is to design a CFG for the language of words that have as many c's as the difference of numbers of a's and b's, that is $\qquad\displaystyle L = \{(a^l)(b^m)(c^n) \mid l, m \in \mathbb{N}...
4
votes
2answers
234 views

Context free grammar construction

My problem with CFG is, I am to generally create ones that don't have requirements such as: $\qquad \{a^m b^n \mid m \le n \le 2m \}$ I have no clue where to begin, and how to approach it. I was ...
4
votes
1answer
2k views

A non-regular language satisfying the pumping lemma

I got a problem to solve, which is to demostrate that the language $L$, given by: $L = \{ab^nc^n\mid n \geq 0\} \cup \{a^kw \mid k\geq 2 \wedge w \in \Sigma^*\}$ Satisfies the pumping lemma. Is not ...
2
votes
4answers
831 views

Is there a *simple* proof that the intersection of a CFL and a regular language is a CFL?

I am following a course on complexity theory where languages are a part of the course. There is a proof that no matter how hard I try to understand, it is till so complex that I cannot make it to half ...
2
votes
1answer
257 views

fixed point in regular expressions

I've posted this question first on StackOverflow but this section seems more suited for this kind of questions. Also I'm not trying to simply solve this exercise (it is a "parsing" exercise, once I'll ...
2
votes
2answers
1k views

Is {xyx | |x|≥1} context-free?

Is $L=\{ xyx \mid x,y \in \{a,b\}^* \text {and } |x| \ge 1 \}$ context-free? If yes, please explain how we can write grammar or create a PDA for it. If not a CFL, then prove it through pumping ...
2
votes
1answer
2k views

Finding a unambiguous grammar

As an exercise we were supposed to find a grammar $G$ that generates language $L(G) = \{w \in \{a,b\}^* \mid |w|_a = |w|_b\}$. That was not so hard, I found a grammar which I think is correct: $S \...
2
votes
3answers
7k views

How does one make an unambiguous context-free grammar for arithmetic expressions?

Say I have a context-free grammar defined by the following rule. $$ \langle EXPR\rangle \rightarrow \langle EXPR\rangle + \langle EXPR\rangle~|~\langle EXPR\rangle \times \langle EXPR\rangle~|~(\...
1
vote
1answer
331 views

Language whose intersection with a CFL is always a CFL

Prove or disprove: If the language $L$ is such that for every context-free language $L_0$, the language $L \cap L_0$ is context-free, then $L$ is regular. I haven't managed to prove this, but I'm ...
1
vote
2answers
557 views

Is it decidable that a context free language contains a given regular language?

I've been asked to solve this problem, but I'm completely stuck now. Is the set $\{G \in\text{CFG} \mid L(G)\supseteq L(A) \}$ where A is DFA fixed beforehand decidable? I know I've to find a ...
0
votes
1answer
2k views

Generating a Context Free Grammar from a Language

I am wondering how to go from a language such as this: L = {a^n b^m c^k | n = m or m != k} To a Context Free Grammar. I know that I would have to turn it into two separate languages but I don't know ...
0
votes
3answers
2k views

How to prove every context-free language over a unary alphabet is regular?

How can I show that every context-free language over a unary alphabet is regular?
0
votes
2answers
3k views

Can we prove that all CFLs can be recognized by a Turing Machine in polynomial time?

This question came up while a group of students at my school were studying for our qualifying exams. The question on an old exam was, Consider the following six classes of languages: Context free (...
-1
votes
1answer
202 views

What kind of subset any class of languages may or may not have?

There are different class of languages, regular,CFL, recursive and r.e. and non-r.e. Clearly a language is set of strings. if an infinite set belongs to any of these classes then what can we say about ...
-3
votes
1answer
133 views

Regular and context free languages

I need to determine if the following languages are regular / context free and to explain. Please help me with that. $$L_1 = \{ a^{i_{1}}b a^{i_{2}}b a^{i_{3}}b a^{i_{4}}b a^{i_{5}}b a^{i_{6}}b a^{i_{...
21
votes
3answers
1k views

Algorithm to test whether a language is context-free

Is there an algorithm/systematic procedure to test whether a language is context-free? In other words, given a language specified in algebraic form (think of something like $L=\{a^n b^n a^n : n \in \...
26
votes
3answers
1k views

Is the language of pairs of words of equal length whose hamming distance is 2 or greater context-free?

Is the following language context free? $$L = \{ uxvy \mid u,v,x,y \in \{ 0,1 \}^+, |u| = |v|, u \neq v, |x| = |y|, x \neq y\} $$ As pointed out by sdcvvc, a word in this language can also be ...
33
votes
2answers
4k views

What does “context” in “context-free grammar” refer to?

There are lots of definitions online about what a Context-Free Grammar is, but nothing I find is satisfying my primary trouble: What context is it free of? To investigate, I Googled "context ...
12
votes
3answers
11k views

The importance of normal forms like Chomsky normal form for CFGs

I understand that context-free grammars can be used to represent context-free languages.It might have ambiguities. We also have normal forms like Chomsky and Greibach normal form. I couldn't ...
5
votes
2answers
898 views

How to get 2-state PDA for CFG?

I'm studying for my Computing languages test and there's one idea I'm having problems wrapping my head around, as far as I know for any Context Free Grammar (CFG), we can design a 2-state Pushdown ...
22
votes
1answer
365 views

Machines for context-free languages which gain no extra power from nondeterminism

When considering machine models of computation, the Chomsky hierarchy is normally characterised by (in order), finite automata, push-down automata, linear bound automata and Turing Machines. For the ...
13
votes
5answers
4k views

How is non-ambuiguity different from determinism?

I am trying to understand what is meant by "deterministic" in expressions such as "deterministic context-free grammar". (There are more deterministic "things" in this field). I would appreciate an ...
7
votes
2answers
1k views

DCFL with prefix property have LR(0) grammar?

There are two important theorems about LR(k) grammars and DCFL. Mentioned here. A language has an LR(1) grammar iff it is DCFL. A language has an LR(0) grammar iff it is DCFL and has prefix property. ...
9
votes
1answer
814 views

How do I reconstruct the forest of syntax trees from the Earley vector?

Using the Earley vector as a recognizer is quite straightforward: when the end of the string is reached, you just have to check for a completed axiomatic production started at position 0. If you have ...
8
votes
2answers
606 views

Myhill-Nerode style characterization of CFL?

Define the Nerode equivalence over a language $L \subseteq \Sigma^{*}$ as $u \sim_L v$ iff $uw \in L \Leftrightarrow vw \in L$ for every $w \in \Sigma^{*}$. The Nerode equivalence ${\sim}_L$ has ...
7
votes
2answers
741 views

Generating a set of minimal-length strings that, together, invoke every production of a context free language

Problem (tl;dr) Given a context free grammar, $G$, find a set of strings that take $G$ through every production it has at least once. How and how fast can it be done? Background I'm working on a ...
6
votes
1answer
1k views

Closure properties of linear context-free languages

Under what operations are linear context-free languages closed? Suppose $L_1, L_2$ are two linear context free languages. Are there any guarantees about $L_1 \cup L_2$, $L_1 \cap L_2$, $\overline{L_1}...
4
votes
4answers
4k views

Prime number CFG and Pumping Lemma

So I have a problem that I'm looking over for an exam that is coming up in my Theory of Computation class. I've had a lot of problems with the pumping lemma, so I was wondering if I might be able to ...
1
vote
1answer
537 views

Pumping lemma for Context-Free Languages

I have a question about a specific pumping lemma problem for Context-Free Languages. Suppose we have the following Language: $L = \{a^{i}b^{j}c^{k}d^{l} \mid 0 < i < k \wedge j > l > 0 ...
7
votes
1answer
1k views

Is the Syntax of C Language completely defined by CFGs?

I think the Question is self sufficient. Is the syntax of C Language completely defined through Context Free Grammars or do we have Language Constructs which may require non-Context Free definitions ...
6
votes
2answers
731 views

Does there exist context-free grammar with words of length n^2 or n^3?

Does there exist context-free grammar with words of length $n^2$ or $n^3$? I can't see any, we can produce all grammar with words of length $n$ ($S \to Se$), but then it seems to be impossible to ...
3
votes
1answer
2k views

unambiguous grammar but it's not LR(1)

I have following grammar: $$A \to a A a \mid \varepsilon$$ This grammar is not ambiguous because it has no more than one parse tree from the any sentence generated by this grammar, but there is a ...
3
votes
2answers
2k views

Why are palindrome and not-palindrome both context-free?

Both palindrome and its complement are context-free. This is very interesting. Both are non-deterministic context-free, which in general are not closed under complement. What is it about these two ...
2
votes
2answers
1k views

Tips for creating “Context Free Grammar” [duplicate]

I am new to CFG's, Can someone give me tips in creating CFG that generates some language For example $L =\{ w v w^R \mid v,w\in \{a,b\}^*\wedge|v| \text{ is even } \}$, where $w^R$ is the reverse ...
2
votes
1answer
951 views

every DCFL has an LR(1), an LALR(1) and even an SLR(1) grammar

Here is one discussion that says, "every DCFL has an LR(1), an LALR(1) and even an SLR(1) grammar." And wiki says, "a language can be generated by an LR(k) grammar if and only if it is deterministic [...