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

learn more… | top users | synonyms

0
votes
0answers
5 views

LL(k) vs Strong LL(K)

What is the diference between LL(K) and strong LL(K) grammars definitions? LL(k): For every pair of production rules A→α and A→β the following condition holds. FIRSTk(αy) ∩ FIRSTk(βy) = ∅ ...
0
votes
2answers
38 views

Proving that a CFG generates a language [duplicate]

Is a suitable way to prove that any given CFG generates (or not) any given language to draw its total language tree? What if the tree is infinite? What would then be a better way to prove that a ...
1
vote
0answers
51 views

Which programming languages can be described by deterministic context-free grammars?

This question asks which programming languages have a syntax that cannot be described by deterministic context-free grammars - the answer is "Many [...] including Algol 60, C, and C++". Until ...
3
votes
1answer
170 views

How to prove that sequences of stack operations are not context-free

By stack I mean the language of sequences it represents, say, a stack with data domains $N$ (natural number) is: $\{ \mbox{push(0)}, \mbox{push(1)}, \mbox{push(0).push(1)}, ..., \mbox{push(0).pop(0)}, ...
3
votes
3answers
86 views

Find member of CFL that is Levenshtein-closest to non-member string

Is there an (efficient?) algorithm which given a context-free language $L$ (given as a grammar) and a string $x$ with $x \not \in L$ computes a $y$ with $y \in L$ and $\forall y': y' \in L \implies d(...
1
vote
1answer
52 views

Is converting an ambiguous grammar to an unambiguous grammar computable?

Is the problem of converting ambiguous grammar into unambiguous grammar computable? (Consider Domain as all context free languages).
-2
votes
1answer
37 views

Find a CFG for palindromes with at most three c's

I'm trying to figure this one out, as I've found the CFG for the palindrome language. I can't work on a solution that also covers #c(w) <= 3. Find a CFG for the language {w∈{a,b,c} | ...
-2
votes
2answers
40 views

If I prove that a language is not a CFL, can I assume it is Turing-Decidable?

Lets say I have just used the pumping lemma to prove a certain L language is not CFL. If it is not CFL can I use that as a proof that it is Decidable? Or is this not enouph and I still have to ...
0
votes
2answers
75 views

Finding Language of a CFG

Say you are given the following CFG $G$: $$ S \to S_1 \mid S_2 \\ S_1 \to AbAS_1c \mid \epsilon \\ S_2 \to BaBS_2c \mid \epsilon \\ A \to Aa \mid \epsilon \\ B \to Bb \mid \epsilon $$ What is $L(G)$? ...
0
votes
0answers
29 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 \\ ...
6
votes
2answers
312 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
58 views

Is $\{a^nb^n\}\cup\{a^nb^{2n}\}$ LR(k)?

I was reading Knuth's paper "On The Translation of Languages from Left to Right", my particular interest being on RL($k$) languages (not a typo). By the end of the paper, he puts the grammar: $$ S \...
5
votes
1answer
72 views

CFG Equivalent of regular expressions

So I was wondering something about the Chomsky hierarchy. DFAs (and NFAs) accept regular languages, while NPDAs accept context-free languages. Right-regular or left-regular grammars produce regular ...
0
votes
2answers
83 views

Is intersection of regular language and context free language is “always” context free language

I have read that intersection of regular language and context-free language is always context-free. Most of the places an standard example has been used to prove this, e.g., \begin{align*} L_1 &= ...
1
vote
1answer
27 views

Preservation of context-free languages under prefix and suffix elimination

Let $\Sigma=\{0,1\}$ be our alphabet. Let $L$ be some context-free language, which is known to start and end with 0's, meaning that every word $x$ in $L$ has a form $x=0y0$. Let $M$ be a language ...
-1
votes
1answer
36 views

Languages reducible to and from context-free

Let $L'$ be a context-free language. If $L \leq_M L' \leq_M L''$, where $\leq_M$ denotes mapping reducibility (aka many-one reducibility), what can we know about $L$ and $L''$? I think they're both ...
1
vote
1answer
52 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
90 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 ...
0
votes
0answers
28 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$,...
2
votes
1answer
33 views

How to use the Pumping Lemma to prove that a restricted subset of 0*1*2*3*, where there are as many 3's as 0's and 1's, is not a CFL?

Use the pumping lemma for context-free languages to show that the following language is not context-free: $ L = \{0^i 1^j 2^i 3^k \mid k=i+j \} $ So I have started like this: Let us assume that $ ...
3
votes
1answer
48 views

Is the word problem of CFLs in NC?

Consider the membership problem for a context-free language. An instance of this problem can be described as pair $(G,w)$, where $G$ is a context-free grammar and $w$ is a string. Lets say I have a ...
0
votes
1answer
40 views

The Chomsky–Schützenberger representation theorem

I've been trying to proof The Chomsky–Schützenberger, but I stuck on creating regular language from that theorem. I mean reagular language, which is intersected with Duck language. Could anyone give ...
3
votes
0answers
56 views

Context free grammar as minimal solution of a system of equations

It is a well-known fact that language generated by a context-free grammar is the minimal solution of a particular system of equations, for example: $$\begin{align*} X &=\{{\epsilon}\} \cup Y\\ X ...
3
votes
1answer
39 views

How to recursively infer a word/string from a context-free grammar?

Give the recursive inference of the word $abcddd$ from the Context-free Grammar: $A\rightarrow aAd\mid B$ $B\rightarrow bBd\mid C$ $C\rightarrow cC\mid cD$ $D\rightarrow Dd\mid ϵ$ This is ...
4
votes
1answer
56 views

How to use Parikh's Theorem to show language is not context free

Parikh's Theorem is quite complicated, I understand intuition of that theorem but I don't see how to use that to prove that language is not context free. I kindly ask you to show me how to do, ...
0
votes
0answers
36 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
2answers
40 views

Proof for TM accepting any PDA-language

How do you suggest I go about proving this: Give a short, basic outline of a proof that Turing machines can accept all languages accepted by PDAs. You are allowed to use a non-standard Turing machine....
0
votes
1answer
71 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'...
14
votes
1answer
336 views

Is language equality for linear context-free grammars decidable?

Let's consider two context-free grammars $G_1$ and $G_2$ and ask the following question: Is $L(G_1) = L(G_2)$, that is, are the two grammars equivalent? In general, this problem is undecidable. ...
4
votes
2answers
491 views

Does a context-free grammar with multiple variables have a “starting” point?

So lets consider the following grammar $$ \begin{align*} S &\to 0 \mid 0A \\ A &\to 1 \end{align*} $$ would the string "1" be accepted by the language or must the language start with $S$?
2
votes
1answer
94 views

How to use a CFG to restrict a subset of a*b*c*d* so that there are at most as many a's and b's as d's?

Give Context-free Grammar for the language $\{a^i b^j c^k d^h \mid i,j,h \ge 0, k>0, i+j \le h\}$ This is a training exercise, for which we don't get any answers, in a course I'm taking. I have ...
1
vote
1answer
78 views

Can every context free grammar be transformed into equivalent grammar of this form?

Show, that every context free grammar can be transformed into equivalent context free grammar ( with possible loss of $\lambda $ ) where $a \in V_t$ and $A,B,C \in V_n $ with rewriting rules of ...
0
votes
1answer
42 views

Context free Grammar and regular set

I read a question and I don't understand it, is the set consisting of: production rules of Grammars that are CFGs, itself a regular set? The only thing I know is that the type 3 is under the type 2 in ...
0
votes
1answer
46 views

Showing a language is context free. Use PDA or CFG?

I am wondering on how to approach a specific problem I am struggling with. I am not understanding which way to approach it and how to solve it. Show language $L$ is context free, where $L = \{\text{...
0
votes
1answer
29 views

Why descriptive power of context-free grammar is greater than regular expression?

Below is a saying from this article. Regular expressions sit just beneath context-free grammars in descriptive power: you could rewrite any regular expression into a grammar that represents the ...
0
votes
1answer
24 views

How can I show context free grammars are strictly more expressive than regular expressions with an example?

I need to show a CFG can express everything that can be expressed by a regular expression, and something that cannot.. I have no idea what example is traditionally used for this.
1
vote
0answers
12 views

How can we avoid mistake in LL(1) parse tree?

I'm learning about LL(1) parse tree. We need to find first and follow in order to construct a LL(1) parse tree. Each and every ...
0
votes
1answer
55 views

If the strings of a language can be enumerated in lexicographic order, is it recursive?

If the strings of a language L can be effectively enumerated in lexicographic order then is the statement "L is recursive but not necessarily context free" is true?
0
votes
1answer
39 views

Determine whether a context-free language is deterministic or not

I define language $L = \{a^k a^m b^m c^k \} \cup \{a^n b^n b^k c^k\}$ and I want to determine if it's deterministic context free language or it is nondeterministic. so I tried to create pushdown ...
0
votes
3answers
87 views

What is the language generated by a given grammar

Given the grammar $s \to aSb \mid bSb \mid a \mid b$; what is the language generated by the grammar over the alphabet $\{a,b\}$? When I was solving this question I was a bit confused about the ...
-3
votes
1answer
47 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 ...
1
vote
1answer
20 views

What is the complement of the language with all ucv with u ≠ v?

If $L = \{w_1cw_2: w_1,w_2 \in \{a,b\}^* , w_1 \neq w_2\}$ what is the complement of language L? one of my friend said that it is $\overline{L} = \{w_1cw_2: w_1,w_2 \in \{a,b\}^* , w_1 = w_2\}$ and he ...
-3
votes
1answer
29 views

clarification about first for cfg [closed]

S-->ABCDE A-->a/ε B-->b/ε C-->c D-->d/ε E-->e/ε i have solved first for above question but a little clarification is required first(S)= first(A)=a/ε first(B)=b/ε first(C)=c first(D)=d/ε ...
0
votes
1answer
29 views

removing ε production

It's not that i dont know how to remove εproduction but when complex problem arises i get confused for example S-->Aa/aaB A-->a/ε B-->bbA/ε CFG without ε production for the above question is S-->...
-1
votes
1answer
26 views

Need help removing ambiguity from grammar

$E \rightarrow UV \bracevert EBE \bracevert V \bracevert [E]$ $V \rightarrow a \bracevert b$ $U \rightarrow < \bracevert > $ $B \rightarrow ? \bracevert ! \bracevert @ $ Order of precedence: ...
3
votes
2answers
53 views

Meta-grammar for context-free grammars

Formal grammars like regular expressions (REs) or context-free grammars (CFGs) specify languages, i.e. sets of strings over an alphabet. Grammars themselves can be seen as languages, e.g. the set of ...
-3
votes
1answer
50 views

Finding the language generated for CFG

What language generated by the following context-free grammar 1) S------> SaS | b i already know the answer to question one but to prove it would is be something like this: S -----> SaaS -----> baab ...
1
vote
0answers
28 views

Decidability Proof of $A_{Cfg}$

I am a beginner to complexity theory and I came up with the following proof of decidability of $A_{Cfg}$ = {$<G,w>|G$ is a context free grammar that generates string $w$} The Turing machine ...
-4
votes
2answers
159 views

odd length palindrome's f=language [closed]

Find the language generated by the following grammar over the input alphabet = {a,b}. S –> aSa | bSb | a | b The language generated by the above grammar over the alphabet {a,b} is the set of (A) ...
0
votes
0answers
42 views

Proof of completeness for CFG having twice as many zeroes as ones [duplicate]

One possible CFG containing twice as many zeros as ones can be, S -> 0S0S1S | 0S1S0S | 1S0S0S | ϵ (This CFG is redundant but it will do the job. So I am not interested in the redundancy. Other ...