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
0
votes
0answers
13 views

If the Pushdown-Automaton for a language is deterministic, is the language non-ambiguous?

For a given context-free grammar (CFG) you can always construct a pushdown automaton PDA (and vice-versa). This pushdown automaton is possibly non-deterministic, since for a non-terminal $X$ in the ...
0
votes
0answers
17 views

How to count the number of nodes for a tree generated by context free grammar derivation?

Given context free grammar I use breadth first search and left most derivation rule to generate all possible words for a given language. For example: ...
-1
votes
1answer
25 views

Can I use the CYK-Algorithm for a Grammar where all results still have a Variable in them?

Let the Grammar be G = ({S}, Σ, P, S), where Σ = {⟨,⟩,[,]} and P: S → ⟨S⟩, [S], SS, ε [⟨ → ⟨[ Can I still use the CYK-Algorithm and if yes then how would I do it ...
-3
votes
0answers
26 views

CFLs are accepted by two-state PDAs w/o $\epsilon$-transitions

Show that if $L$ is accepted by a PDA, then $L$ is accepted by a PDA having at most two states and no $\epsilon$-transitions.
1
vote
1answer
31 views

Disambiguating grammar for Dyck language

Given the following simple grammar for a language that contains all strings with matched parentheses: \begin{align} &s \to ss \\ &s \to (s) \\ &s \to () \end{align} Examples: $(), ()(), (()...
0
votes
0answers
18 views

Make case expressions unambiguous

Given the following context free grammar: ...
0
votes
1answer
32 views

Show that if L is CFL and R is a regular language then {w ∈ Σ^∗ | xw ∈ L for some x ∈ R} is context free

Show that if $L$ is CFL and $R$ is a regular language such that they both share the same input alphabet $\Sigma$, then $C = \{w \in \Sigma^*\mid xw \in L$ for some $x \in R\}$ is context free. Hi I'...
0
votes
1answer
37 views

Remove left recursion from a grammar without necessarily removing epsilon production

Consider the grammar $$S →Aa∣b$$ $$A →Ac∣Sd∣ϵ$$ Construct an equivalent grammar with no left recursion and with minimum number of production rules. $\tag {GATE-CS-1998}$ While solving this question, ...
1
vote
2answers
48 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 ...
0
votes
0answers
26 views

Complexities of algorithm for generating strings of length k from CNF grammar

Question: For the code "generate_language_rec" below, explain whether the time and space complexities are Linear, Polynomial or Exponential ( find a tight upper-bound ) in $k $. Assume the ...
0
votes
0answers
42 views

Construct PDA for $\{a^ib^j\ | i > j \ \& \ i < 2j\}$ [duplicate]

How to construct PDA for language $\{a^ib^j\ | i > j \ \& \ i < 2j\}$? I know how to check first and second conditions separately but at once there's a problem.
0
votes
1answer
25 views

Prove that $L =\{ a^n b^m c^{n\times m} \mid n, m\geqslant 0\}$ is not context free

I looked at all possible options for $vx$ when you look at $z = uvwxy$ and can't find a contradiction in the case where $b$'s and $c$'s are in $vx$.
0
votes
0answers
25 views

Decidability of the language of a regular expression being a subset of a given context free language

Let L be a language of pairs $\langle R,G\rangle$, with the first element being a regex and the second being a CFG. Is it decidable that G accepts whatever the regular expression does? In other words, ...
1
vote
1answer
36 views

Is there a way to show that if the description of a language depends on some kind of global structure, then it isn't a CFL?

So I've been reading Sipser's theory of computation book, and I've come across the pumping lemma for context-free languages, which as a reminder says that if a language is context-free, then there is ...
1
vote
1answer
46 views

PDA for $\{a^nb^m \mid 0 < n \le m \le 3n\}$

I have to design a PDA that recognizes the language $\{a^nb^m \mid 0<n\leq m\leq3n\}$ I tried to partition the stack into 3 partitions with the first partition being the size of $n$ with character ...
0
votes
1answer
33 views

Reduce-reduce conflict in SLR vs LALR

I was wondering if I could say any of the following is true. Given a grammar $G$, If the LALR parser has reduce-reduce conflict for $G$, then the SLR parser also has reduce-reduce conflict for $G$. ...
0
votes
1answer
130 views

Context free grammar for $1^n 0^m 1^k 0^p$ where $n+k=m+p$

i need to convert this CFL to CFG $$ L = \{\; 1^n 0^m 1^k 0^p \mid n\ge 2, k,m,p\ge 1, n+k=m+p\;\} $$ I am trying to solve this problem for a few days but i couldn't. Is there anyone to help me? I'm ...
2
votes
1answer
39 views

Is the union of two CFLs minus their intersection a CFL?

I've seen the classical proofs of CFLs are not closed under intersection or complement, but I haven't been able to wrap my head around this. Intuitively, I think that this would be not a CFL but I can'...
0
votes
1answer
40 views

Any context-free grammar generating a regular language is unambiguous

I am not sure whether this statement is true or not. Could there be an example of CFG generating a regular language and is ambiguous?
0
votes
0answers
38 views

Complement of a context free language

Consider the context-free language of balanced parentheses of three kinds: $$L = \{w \in \{ (, ), [,], \{, \} \}^∗ \mid \text{all parentheses in }w \text{ are properly balanced}\} $$ What will be the ...
-1
votes
1answer
19 views

Is a one step derivation grammar context free?

Suppose we have a grammar having a one step derivation like S -> a where 'S' is a variable and 'a' is a terminal. Since this grammar does not pump terminals, can we say that the language generated ...
0
votes
0answers
16 views

Find CFG for bin(n)bin(2n+3)^R

Where bin(n) is the shortest binary representation of n. First, we can see that we can rewrite it as $bin(n)bin(2(n+1)+1)^R$ which implies that the second word will always start from 1. We can also ...
0
votes
0answers
24 views

Pumping Lemma for CFG $S \to c|aSdSb$

I've given the grammar $G=(\{S\}, \{a,b,c,d\}, \{S\to c \mid aSdSb\}, S)$ and I wanted to make an expression out of it. I tried bringing it into ChomskyNF, but as someone commented below the approach ...
0
votes
0answers
57 views

Construct CFG of monadic logic

How to construct CFG for tautologies in monadic predicate logic in the empty model. The predicates are Q and P, operations are ...
1
vote
1answer
38 views

Decidability for intersection of context free and regular languages

I am wondering if the following are decidable or undecidable and why. L is a CFL and R is a regular language. How does the complement of the context-free language change the decidability of the ...
0
votes
3answers
65 views

Making a simplest possible CFG to recognize the language L = {a^i b^j c^k | i + j ≥ 2k}

The language given is $L = \{a^i b^j c^k\mid i+j \ge 2k\}$ for which I need to construct a simplest possible Context Free Grammar. I tried understanding but I could only go as far as making sense of $...
0
votes
1answer
47 views

How to design PDA for this language?

I'm having a hard time trying to build the PDA for this language: $$L=\{a^nb^m: n,m \geq 1 \land m=4n+2\}$$ I don't know how many $a's$ should I push into the stack when reading $a$, and how many $a's$...
0
votes
1answer
34 views

References to deterministic time complexity of language classes

It's fairly well known that $REG \in TIME(n)$. I would like to know similar inclusions for the language classes $DCFL$ and $CFL$. I have found a variety of claims for these classes on the internet. ...
0
votes
2answers
59 views

Equivalence relation between two CFG's

In our course: Automata and Computation there is a definition about Context-Free Grammars which states: "Two CFG's $CFG_{1}$ and $CFG_{2}$ are equivalent if $L_{CFG_{1}} = L_{CFG_{2}}$ where $L_{...
-3
votes
1answer
27 views

Decoding CFG for odd length string-:

S → aX | bX X→ aS | bS | ε This is required cfg, I want to learn how we arrived at this cfg? What steps did we follow to arrive here? Do we memorize some standard ...
0
votes
1answer
59 views

What happens to a Turing Machine if it enters final state but the input is not yet read completely?

In the image, the language of the TM is defined on (a, b, c, d) and there is no transition on final state, but strings consisting of d are also part of the language. In all TM problems I have seen ...
0
votes
1answer
26 views

Empty string in an ambiguous grammar?

I'm a bit confused by the role of the empty string in this ambiguous grammar: A' -> A A -> if A B A -> null B -> [empty string] B -> else S So what ...
-1
votes
1answer
38 views

I can't visualize what happens when we pump v and y in pumping lemma for $a^n b^n c^n$

If you need some context-: https://www.andrew.cmu.edu/user/ko/pdfs/lecture-11.pdf around page 7. Case 1-: Say vxy contains ab So when I pump v and y, what will get pumped? And how the result would be. ...
1
vote
1answer
31 views

CFG for L={a^i b^j c^i; i,j > 0}

I worked a bit on this and got this-: S->ABC A->aA/a B->bB/b C->cC/c The obvious problem here is I am unable to count number of a's and c's which ...
0
votes
2answers
119 views

Can I solve pumping lemma for context free language proofs using examples?

Say I need to prove that $L=${$a^n b^n c^n; n\geq 1$} is not context free language I take n=3. w=aaabbbccc Here |w|=9. we know by pumping lemma-: |vxy| $\leq$n so vxy=abb |vy| $\geq$1 so vy=ab Hence I ...
0
votes
0answers
13 views

Tips on making a grammar LL(1)?

So I currently am given the following grammar, and I have to make it LL(1). To do this, I need to remove ambiguities, eliminate left recursion, and left factor if necessary. But looking at this, it's ...
0
votes
1answer
19 views

What is the subset of CFGs called where each expansion must be the same?

I was wondering about a kind of grammar where we can expand rules of the form A -> X|Y|... with A being a nonterminal and <...
1
vote
1answer
48 views

Is language $a^mb^nc^n, m \not= n$ context free

I need to say Is language $a^mb^nc^n, m \not= n$ context free I managed to find a grammar for $L1 = $ { $a^lb^mc^n | l=m$ or $m = n$ }, but I couldn't find the one I needed. Maybe it is impossible, ...
1
vote
2answers
48 views

PDA with multiple element access - $i$ - access PDA

We define an $i$ - access PDA as a PDA that can manipulate the top $i$ characters in the stack, where $i>0$. Given a transition function of the form $\delta(p,x,c,d) \to (q,c')$, where $d \le i, d &...
0
votes
1answer
24 views

Variant of Chomsky Normal Form for Languages with Strings of Length $\ge 2$

Given a context-free grammar $G$ for a language $L$, where $L$ contains strings of length greater than 2, show that there exists some context-free grammar $G'$ which generates $L$ such that every rule ...
2
votes
1answer
45 views

Proving that the given Context free grammar generates strings with unequal number of a's and b's

Here is the grammar given on the wikipedia: $$ S \rightarrow T \;|\; U \\ T \rightarrow VaT \;|\; VaV \;|\; TaV \\ U \rightarrow VbU \;|\; VbV \;|\; UbV \\ V \rightarrow aVbV \;|\; bVaV \;...
0
votes
1answer
78 views

Why is it undecidable to check the emptiness and finiteness of a context-sensitive grammar?

Context-sensitive languages have context-sensitive grammars, and context-free languages have context-free grammars. Using context-free grammars, we can decide the finiteness and emptiness of context-...
0
votes
1answer
43 views

Difference between Counter-machine and stack machine

I read from this question that counter automata is a push down automata with only one symbol allowed on the stack (plus a fixed bottom symbol). My question is counter machine means counter coexist ...
0
votes
0answers
55 views

Whether $L(G)=L(R)$ is decidable for DCFL and CFL?

Let $G_1$ be the context free grammar and $R$ be regular language. Now I have to check whether $L(G_1)=L(R)$ is decidable or not? My approach $\overline{L(G_1)}=\overline{L(R)}$. Now $L(G_1)$ not ...
0
votes
1answer
100 views

Rice theorem could apply except RE language?

You know that Rice theorem is applicable to check decidability of RE language. Also we know that all regular, deterministic context free, context free, recursive languages are RE languages. $Q_1:$ So ...
0
votes
2answers
161 views

Regularity of CFG and DCFL

I read that it is undecidable whether, given a CFG $G$, $L(G)$ is regular. And there exists no algorithm that, given a CFG $G$ such that $L(G)$ is regular, outputs a DFA that accepts $L(G)$. My ...
0
votes
1answer
46 views

Why finiteness problem of CFL is decidable?

We know that every $CFL$ has infinite configuration space. Due to this equality problem is undecidable. But why finiteness property is decidable inspite having infinite configuration space?
1
vote
1answer
66 views

Why equality is decidable for regular language but not for $CFL?$

There are infinitely many different $PDAs$ for the same $CFL$ exist, therefore we can't check equality for $CFL.$ But also there are infinitely many different $DFA$ exists for same regular language. ...
0
votes
1answer
48 views

Is set of all RE languages $\subseteq\\$ $\Sigma^{*}?$ [closed]

We know that any languages $\subseteq\\\\$ $\Sigma^{*}.$ Because any language collection of string over alphabet. And we know that set of all languages is $2^{\Sigma^{*}}$ which doesn't $\subsetneq\\\\...
1
vote
1answer
70 views

Stuck with shift-reduce conflicts on yacc on grammar to generate palindromic strings on {0,1}

I have written a yacc program for generating palindromic strings consisting of 0s and 1s. Here is the rules section of the yacc program below: ...

1
2 3 4 5
31