Questions tagged [context-free]

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

201 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
1
vote
1answer
263 views

Converting indirect recursion to direct one

I want to remove left recursion in grammar: $G = ({S, A,B,C,D}, {a,b,c},P,S)$ $S → A$ $A → Aa | Bc$ $B → B a |CD$ $C →C b | ε$ $D → Bb | a$ We see that this grammar contains direct recursion ( $...
1
vote
1answer
128 views

LL(1) CFG for triple amount of b's compared to a's?

I would like to construct a LL(1) context-free grammar for a formal language $A$ = "strings where the amount of character b is exactly triple compared to the amount ...
1
vote
1answer
210 views

Is $\{u u^R u : u \in \Sigma^*\}$ context-free?

Given a finite alphabet $\Sigma$ with more than one symbol, is $L = \{u u^R u : u \in \Sigma^*\}$ context-free? ($u^R$ is the reverse word of $u$) I tried to show it wasn't context-free by using the ...
0
votes
0answers
11 views

Undecidability of an Intersection

1)"Given a CFL L and a regular language R, is the intersection of L and R an empty set?" decidable? 2)What if we replace L with the complement of L? Either 1 or 2 is decidable and the other ...
0
votes
0answers
38 views

Eliminating ambiguity in $A \to AA \mid (A) \mid a$

I'm trying to solve this complier design problem related to ambiguity in CFG the given grammar is \begin{align} &A → AA \\ &A → (A) \\ &A → a \end{align} I was able to find that this ...
0
votes
0answers
23 views

How to change a grammar so that it can be unambiguous?

The original grammar is $$ S \to SaS \mid SbS \mid ScS \mid d $$ My answer is $$ S \to daS \mid dbS \mid dcS \mid d $$ Is that correct?
0
votes
0answers
23 views

Need some guidance on CFG pumping lemma proof

I'm currently stuck on a homework problem, and I feel completely lost about how to solve it. Generally I find pumping lemma proofs to be pretty straight-forward, but I feel like I'm missing something ...
0
votes
2answers
82 views

Is $L = \{ a^ib^j : 0 < j < i < 2j\}$ context free? How can it be shown?

Is $L = \{ a^ib^j : 0 < j < i < 2j\}$ context free? If so, can there be a pushdown automaton described for it? If not, does the pumping lemma apply?
0
votes
1answer
29 views

Can PDA accept only by final state without finish reading input?

I am defining, a string $w$ is accepted by a PDA whenever the PDA enter into a final state during the computation(at least on one branch of the computation) on the input $w$ (no matter whether the ...
0
votes
0answers
72 views

Draw a CFG (context-free-grammar) that starts and ends with the same symbol yet has odd number of 1's

I figured out that the CFG that starts and ends with the same symbol in alphabet $\Sigma=\{0,1\}$ will be : S -> 0A0|1A1|0|1| A -> 0A|1A|𝜖 How can i interpret the odd number of 1's also?
0
votes
1answer
102 views

I'm trying to prove this language is not context-free: {a^x b^y c^z | where x=z and x<y}

So far i've tried with making x = z = p and y = 2*p, but it seems that if I place vxy to represent all b's then I can't get a contradiction.
0
votes
1answer
49 views

What to do following a reduce in LR(1) parsing?

I am using this standard question from Dragonbook as an example, (the first problem) . I have trouble with what happens in State 4 on LR(1) parsing. Once it is reduced by the rule C->d, now what ...
0
votes
0answers
36 views

Context-Free Grammar Question

Given a regular Expression: 0^a 1^b 0^c, where a+b=c and a,b,c >= 0. Find the cfg for this expression. Here is what I tried to do: s -> AsB A -> 01 B -> 0 But then a language could be ...
0
votes
0answers
21 views

Constructing a Push Down Automaton

Given a 7 tuple push down automaton M = (K, Σ, Γ, Δ, s, F) where K = {p, q, r}, Σ = {a, b, c}, Γ = {a}, s = p, and F = {r}, with the transitions ((p, b, ε), (q, ε)), ((q, a, e,), (p, a)), ((p, c, a), (...
0
votes
0answers
17 views

Constructing a context free grammar with starting state

I'm supposed to construct a context-free grammar generating all strings in : {(ab)$^{m}$c$^{n}$(ba)$^{m}$ : m, n, ≥ 0} So far I have V = {A, S, a, b, c}, Σ = {a, b, c}, and R = (1) S -> A (2) S -&...
0
votes
0answers
54 views

How to show $L = \{0^{i}1^{i^{2}}| i \ge 0\}$ is not context-free using pumping lemma

I've been struggling with this problem for quite a while now and don't really understand what to do for the pumping lemma here. We have the language $L = \{0^{i}1^{i^{2}}| i \ge 0\}$ and we need to ...
0
votes
0answers
18 views

Do the SLR and LALR parsers of a same CF grammar have the same shift actions?

In theory, given that: The LALR parser can be constructed by merging LR(1) states with the same core; If $I$ is a LR(1) set of items, then $\text{core}(\text{GOTO}(I))=\text{GOTO}(\text{core}(I))$; ...
0
votes
0answers
13 views

Derivation tree and Productions from left most derivation of string

How can one find Derivation tree and Productions of a Grammar from left-most derivation and string used? I was given input string x = abaccacaa , left most derivation lder(x)=(1,2,1,3,4,1,3,5) and two ...
0
votes
0answers
16 views

Empty LBA why all the configurations must be all equal

While trying to prove the Empty LBA one of the rules says that for having a computational story you have the 3 rules : and one of the 3 rules says that Ci has to produce Ci+1 and all the ...
0
votes
0answers
51 views

The class of grammars recognizable by backtracking recursive-descent parsers

It is easy to show that there exists a grammar that can be parsed by a recursive-descent parser with backtracking but is not an $\text{LL}(k)$ grammar (consider any grammar with a production featuring ...
0
votes
0answers
32 views

Why is there no contradiction when using pumping lemma on a^N b^N a^2N, when k=2?

I have question where it asks: Using the pumping lemma on a^N b^N a^2N, why can you not reach a contradiction when k=2? Here's what I've done, but I do reach a contradiction... u=a^r v=a^s x=a^t b^N a^...
0
votes
0answers
67 views

GATE CSE 2018, Which of the following languages are context-free?

A] {ambncpdq | m+p = n+q, where m, n, p, q >=0} B] {ambncpdq | m = n and p = q, where m, n, p, q >=0} C] {ambncpdq | m = n = p and p not= q, where m, n, p, q >=0} D] {ambncpdq | mn = p+q, ...
0
votes
0answers
64 views

Is it necessary for a Push down Automaton (PDA) to have a stack?

I am given a Finite Automaton and the question is to design an Equivalent PDA for it. This is my FA: Is this PDA correct or do I need to add a stack to it? If its right when is the stack needed?
0
votes
2answers
60 views

Build PDA for a language with unknown input alphabet

$L_1 ,L_2$ are regular language. We form a new language $L_{12}$ as follows: $L_{12}=\left \{ w_1\cdot w_2|w_1\in L_1\wedge w_2\in L_2\wedge|w_1|=|w_2| \right \}$ In this exersice I am not given any ...
0
votes
0answers
50 views

How to show that language L is NOT context-free?

True or false: To show that a language L is not context-free, one can alternatively show that the union between L and a known context-free language is not context-free. I know that you can prove ...
0
votes
2answers
207 views

How to remove null production from context free grammar?

How to remove null production and simply the grammar? $$ S \to a \mid Ab \mid aBa \\ A \to b \mid \epsilon \\ B \to b \mid A $$ Can the simplification result in this CFG? $$ S \to a \mid aBa \\ A \to ...
0
votes
0answers
13 views

Does all derivation trees generated by context free grammar in cnf form can be recognized by buttom up tree automata?

G is a context-free grammar in Chomsky normal form. we define L(G) to the set of all derivation trees that formed by G. Is it possible to create a non-deterministic bottom-up tree automaton that will ...
0
votes
0answers
63 views

What does it take to create a new programming language and its toolchain?

I am super novice to this topic, so my apologies if my question looks completely nonsense to you all! Imagine you want to create a new programing language that transpiles to a more common high/low-...
0
votes
0answers
28 views

Upper bound on size of derivation in CFG

Suppose $G$ is a $CFG$ with $m$ variables, in which the right-hand side of all production rules has length at most $\ell$. Show that if $A\Rightarrow^*_G\varepsilon$, then there is a derivation of no ...
0
votes
0answers
58 views

Convert PDA by final state in to cfg

Hope you all are doing well. I want your assistance. I have a PDA which is accepted by the final state. I need to convert it into cfg. So I want to ask, If I want to first convert this into ...
0
votes
0answers
33 views

Context free grammar to Chomsky normal form

I have a hard time understanding how to convert the following context free grammar to Chomsky Normal Form: S $\rightarrow$ aSX | B B $\rightarrow$ bBX | ε X $\rightarrow$ a | b I have a solution S $\...
0
votes
0answers
65 views

Is language bin(n)bin(2^(k+1) n + 1)^R context-free

I have a problem with this exercise. For language $$L_1 = \{ w \in \{0, 1\}^* : \exists k \in \mathbb N \ w = \text{bin}(n)(\text{bin}(2^{k+1}n + 1))^R \},$$ where $\cdot^R$ reverses a string and $\...
0
votes
0answers
29 views

Making context-free grammar unambiguous

I'm trying to change below context free grammar such that it becomes unambiguous, but I don't know what steps I should take. Is there any specific way of doing that? Here is my CFG: \begin{align} &...
0
votes
0answers
45 views

generate CFG from words that have even length and have at most two 0's

How to I generate a CFG from the language that have even length and have at most two 0’s L3 = {w ∈ {0, 1} ∗ | w is even length, 0<=2 } I feel stuck on meeting the criteria of maximum two 0s My ...
0
votes
0answers
42 views

Given a CFG and one of its nonterminals $v$ determine if there exists a sentential form beginning with $v$?

I am supposed to find an algorithm solving the following problem: Given a CFG $\;G=(V_N, V_T, R, S)$ and a nonterminal $v \in V_N$ determine if there exists a sentential form which begins with $v$. ...
0
votes
0answers
46 views

Is there a pda with maximum 3 state for every CFL?

This is the first question I'm asking here I'm trying to understand whether we can construct a PDA with a maximum of 3 states for every possible CFL or not? if so how?
0
votes
0answers
73 views

how to write a language for context-free grammar generates the empty string?

How would you write a language for a context-free grammar that generates an empty string. Is it something like E = { (G) | G is a CFG and L(G) = Ø}?
0
votes
0answers
27 views

Context free grammar Help

I need to create a CFG for the following language: $$ \{a^ib^jc^k|i≤j≤2i, k=2j\} $$ Getting the a's and c's to be correct is easy enough but everything else is confusing me slightly. any help would ...
0
votes
0answers
38 views

How to include both precedence and associativity in following grammar?

For the following grammar, how can I include both precedence and associativity of operators: S -> S|S S -> S.S S -> S* S -> (S) S -> a|b Note: In the first rule ...
0
votes
0answers
152 views

Why is a Context Free Grammar that is simultaneously in Chomsky Normal Form and Greibach Normal Form regular?

In my course materials, there is one sentence about how if CFG is in Chomsky Normal Form, it is not regular, and if it is in Greibach Normal form, it also is not. But when a grammar is simultaneously ...
0
votes
0answers
58 views

I´m having problems with this Context Free Grammar

I am not able to convert the following language to a Context Free Grammar. The major problem is how to pump both "sides" of the word to obtain same number of 0s and 1s, but, without creating a series ...
0
votes
1answer
74 views

Using the pumping theorem to show that this language is not context-free

Let $\sigma = \{a,b,c\}$ and let $L = \{s | s = a^jb^jc^k\}$ where $k=i\cdot j$ and $i,j \geq 0\}$. Using the pumping theorem, prove that $L$ is not context-free. I really don't know where to start, ...
0
votes
0answers
43 views

Use the pumping lemma for context free languages to prove L = {w#w | w \in {a,b}*} is not context free

I know the basics of using the pumping lemma for CFG to prove a language L is not context-free, however, the # symbol seems to be throwing me off or my understanding is not complete.
0
votes
0answers
56 views

Pushdown Automata for number of a less than 2 times number of b

Suppose we want to design a pushdown automata for $L=\{x \in \{a,b \}^{*}:|x|_a<2|x|_b \}$, can anyone check whether my automata works? we have 4 states $\{q_0,q_1,q_2,q_3 \}$, three stack symbols ...
0
votes
1answer
379 views

How to determine valid handle for given bottom up parser?

I came across following question: Consider the grammar: $E → E + n\text{ | }E × n\text{ | }n$ For a sentence n + n × n, the handles in the right-sentential form of the reduction are (...
0
votes
0answers
206 views

Conversion of left-recursive context-free grammars to strongly equivalent ones without left-recursion

It is a well-known problem that many top-down parsers have problems parsing a context-free grammar with left recursive rules. There exist algorithms to convert grammars with direct or indirect left-...
0
votes
0answers
206 views

What does pump down means in this solution?

Problem text (from Sipser's "Introduction to the Theory of Computation"): 2.42 Let $E = \{1,\#\}$ and $Y = \{ w \mid w = t_1\#t_2\# ...... \#t_k \, \text{for $k \geq 0$, each $t_i \in 1^*$, ...
0
votes
0answers
57 views

Is there any grammar parseable by LALR(1) but not LR(1)?

https://en.wikipedia.org/wiki/LALR_parser - as far as I understand, LALR(1) is a simplified version of LR(1), aiming to achieve a greater parsing performance at the expense of reduced power. So, IIUC, ...
0
votes
0answers
204 views

The rightmost derivation is possible with the same rule of leftmost derivation

Can someone please help me in understanding the statement. What does it exactly mean? What I think it means is that: the derivation produces by the leftmost derivation is also possible with rightmost ...
0
votes
0answers
57 views

Grammar for context free language

I want to give a grammar for the following language: $$L = \{x^r \# y |x, y \in \{a, b, c\}^*\\ \text{ and }x\text{ is a contiguous sub-string of }y\}$$ where $x ^ r$ denotes the backward written ...