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
4
votes
6answers
16k views

Context-free grammar for language with unequal numbers of a and b

I've been trying to get a CFG for the language of all words with unequal numbers of a and b, i.e. $$\{u \in \{a, b\}^* \mid \text{number of occurrences of $a$ and $b$ in $u$ are unequal} \},$$ but ...
0
votes
0answers
11 views

What's the context-free grammar for { w | 2*(number of a's in w) != 3*(number of b's in w) +2 }? [duplicate]

So I have this language: $$ A= \{ w \in \{a,b\}^* \mid 2*\#_a(w) \ne 3*\#b(w) + 2\} $$ I know it's context free, I know how to make a PDA for it, I just can't, for the life of me, figure out how to ...
2
votes
1answer
71 views

Fitting a regular grammar to strings from a PCFG: how big does it get?

Let $G=(V, \Sigma, R, S)$ be a (non regular) probabilistic context-free grammar, and $u_1, \ldots, u_n$ a set of $n$ strings generated by $G$. For finite $n$, it is always possible to find a regular ...
0
votes
2answers
55 views

How can I efficiently construct a CFG from a language

I am new to CFG's and automata in general and I came across an exercise where I needed to construct a CFG for the language {a^m b^n | n <= m + 3}. So m can be infinitely bigger than n but n can ...
0
votes
1answer
24 views

If one of the case obeys all rules of Pumping Lemma, can we conclude there is no contradiction?

I am studying Pumping Lemma for Context Free Languages, wherein, I am slightly confused in a question where one of the case doesnt obey all rules but another case does. What's the conclusion? Do we ...
0
votes
1answer
63 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, ...
10
votes
1answer
356 views

Shift-resolve parsing - questions

I've recently came across a paper describing the parsing technique mentioned in the title. Unfortunately, the terminology used in said paper is somewhat beyond my comprehension, so I've been ...
0
votes
0answers
16 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
12 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 ...
3
votes
3answers
145 views

Decide if this language is context free

I got this question for homework: Decide if this language is context free or not: $\qquad \{x@1^m: x \in \left\{0,1\right\}^*, m \in \mathbb{N}, x_m = 1\}$. Intuitively I think it's not context-free ...
3
votes
0answers
34 views

BNF rule to regular expression

I'm looking for a way to find out whether a specific rule in a BNF grammar can be converted to a regular expression. (With "regular expression" (RE), I mean the simple mathematical kind. I'm ...
21
votes
4answers
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 \...
22
votes
2answers
410 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 ...
1
vote
3answers
680 views

Context-free grammar for binary words

I am supposed to create CFG for this languague: $L= \{w : w \in \{a, b\}^*, |w_b| = 3k, k \geq 0 \}$ where $|w_b|$ is count of terminals $b$ in $w$. For example: aa - OK, no 'b' abb - wrong, only ...
0
votes
0answers
15 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 ...
1
vote
2answers
32 views

The intersection of 2 CFL

I have the following two CFL: $A =\{a^m b^n c^n\}$ and $B = \{a^m b^m c^n\}$. I don't understand why the intersection of this languages is $\{a^n b^n c^n\}$: can anyone explain to me why the power is ...
1
vote
1answer
53 views

Correct application of the CFL Pumping Lemma

I came across this question about showing that the language $L = \{w \epsilon \{a, b, c\}^*: n_a(w) + n_b(w) = n_c(w)\}$ is context-free but not linear in the book by Peter Linz. That is easily doable ...
1
vote
2answers
131 views

CFG - Left factoring in recursive nested productions

I'm attempting to convert a CFG into an LL(1) grammar for predictive parsing in a compiler. I've been able to left factor and eliminate left recursion and ambiguity for every case in the grammar, with ...
0
votes
2answers
48 views

Does there exist an algorithm to generate the production rules of CFG, given a sample production?

Lets say, we provide the algorithm a set of tokens. e.g. x + y - z x - x - x It will then try to generate a CFG which fits all the provided examples ...
0
votes
2answers
39 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
1answer
77 views

Algorithmic problem of regular, context-free, and recursively enumerable languages

Consider a language $L_1$ that is recursively enumerate, $L_2$ that is regular, and $L_3$ that is context-free. Are the following problems algorithmically decidable? Is $L_1 \cap L_2 = L_3$? Is $L_1 \...
0
votes
1answer
37 views

Why is this language *not* pumpable? (language = arbitrary word followed by exact same arbitrary word)(pumping lemma for context-free-languages)

language = arbitrary word followed by exact same arbitrary word = u * u (with u being out of non-empty words of alphabet {0, 1} ) (sorry for the formatting, see screenshot-link for conventional/clear ...
0
votes
1answer
460 views

LL1 parsing algorithm for strings generated by a given grammar

How to describe a $\operatorname{LL(1)}$ parsing algorithm for strings generated by a given grammar? I have to design a parser for a specific grammar. Let $G$ be the grammar described as: $$S \...
0
votes
0answers
40 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
2answers
171 views

Context free grammar problem for number of a's is twice the number of b's

Can you to find for me a context free grammar for the following language? $$\{w\in\{a,b\}^*: \#_a(w)=2\#_b(w)\} $$ Here $\#_a(w)$ counts the number of $a$'s in $w$.
0
votes
0answers
25 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
1answer
53 views

Converting PDA to CFG

I am trying to understand this example of converting PDA to CFG but I am not getting the idea quite right. I do have the general understanding of theorem that if $p,q\ \epsilon\ Q $ and $X \varepsilon\...
-3
votes
2answers
10k views

GATE CS 2009, question 11, does the grammar produce odd-length palindromes? [closed]

This is question 11 from GATE CS 2009. Find the language generated by the following grammar over the input alphabet = $\{a,b\}$. $S \to aSa \mid bSb \mid a \mid b $ The language generated by the ...
0
votes
0answers
39 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
2answers
725 views

aⁿbⁿcⁿdⁿ using 2-stack PDA

I need to construct a PDA using 2 stacks for accepting the language $L = \{a^nb^nc^nd^n | $ $n \geq 0\}$. Pushing $a$'s to first stack and $b$'s to second and poping them for corresponding $c$'s and ...
0
votes
1answer
29 views

PDA kleene star construction

I know how to prove that CFL are closed under kleene star operation using CFG. I can't find online or in class notes a proof using PDA. I would appreciate description of the basic idea (not formal).
14
votes
1answer
456 views

Is the language of words that are unbalanced in the first half context-free?

(Practice exam question in computational models) Definition: A word $w\in \{0,1\}^*$ is called balanced if it contains the same number of $0$s as $1$s. Let $L = \{w\in \{0,1\}^*\mid |w|$ is even and ...
0
votes
1answer
47 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 ...
2
votes
1answer
128 views

Language of CFG: $S \to aS | aSbS | \varepsilon$

I'm trying to prove that the language L generated by the CFG $S \to aS | aSbS | \varepsilon$ is the language $L=\{ w \in \{a,b\}^*: \text{every prefix of $w$ has at least as many $a$'s as $b$'s} \}$.I ...
2
votes
1answer
26 views

Context free languages invariant by “shuffling” right hand side

Given a grammar $G$ for a Context Free language $L$, we can augment it by "shuffling" the right hand side of each production, e.g.: $A \to BCD$ is expanded to $A \to BCD \; | \; BDC \; | \; ...
3
votes
1answer
97 views

If $A$ is context-free then $A^*$ is regular

I am currently studying for my exam and I am having trouble to solve this question: Right or wrong: If $A$ is context-free then $A^*$ is regular. I think it's wrong because if $A$ is context-free it ...
0
votes
1answer
97 views

Removing left factoring from Context-Free Grammar

I know that, removing left factoring is a simple task. And i understand following procedure: $S→aA | aB$ Becomes: $S→aS'$ $S'→A|B$ Yet I'm running into problems with this particular grammar: $S→AD|...
0
votes
1answer
23 views

Is it possible to form a PDA for this language?

$$L=\left \{ a^nb^m|n\leq m\leq 2n \right \}$$ Is this even context free? I am asking because by looking at the condition, for an expression that holds:$n< m<2n$ can be written as : $a^nb^nb^c (...
0
votes
1answer
22 views

How can I combine 2 PDA's into 1

I need to form PDA for this language: {$a^nb^m|n=m \vee n=2m$} I know the idea of building each one separately but how do I combine them into 1 PDA? LHS: for every 'a' I push 'A' inside stack and for ...
0
votes
1answer
159 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
44 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
1answer
91 views

CFG-Infinite recursion

As you see, the string production process never ends. Can someone explain me if this language is regular or not ? $ S \to Α Β S $ $ A \to S $ $ B \to a B b $
1
vote
1answer
39 views

CFG that generates $1^*$ is decidable

I read somewhere that the problem which asks whether or not a $CFG$ $G$ generates $1^*$ is decidable. The proof goes like this: $1^* \cap G$ is context free since it is the intersection of a regular ...
1
vote
2answers
91 views

Need help understanding what co-recursively enumerable means

Lets say I have a set: $ L = \{\langle G \rangle | L(G) = \Sigma^{\star}\}$ and the question asks if it is co-RE. I know that if something is co-RE, it halts on every input not in L but may or may not ...
0
votes
1answer
27 views

Is there any property about height of PDA?

I'm trying to find a PDA for $L$ which modifies the stack height at most one. $L=\{a^ib^i\mid i\geq 0\}$ I think there is no such PDA but how can I prove it? My attempt is for a given string, find ...
1
vote
1answer
47 views

Help with context free grammar excercise

So, I have an exercise in which I have to write a context free grammar for this language: $$L = \{x \in L(a^∗b^∗c^∗) : |x|_a > |x|_c; |x|_b > 0; |x|_c ≥ 0\}$$ meaning every string with any ...
1
vote
1answer
30 views

Why is the following grammar not LL(1)

Consider the following grammar: S → bAb | bBa A → aS | CB B → b | Bc C → c | cC I have to provide the reasons as to why this grammar is not LL(1). So far ...
0
votes
2answers
26 views

Is the language of rectangular matrices in MATLAB-style syntax context free?

Consider the language $L$ of rectangular matrices written down as a comma separated list of integers where each list represents a row of the matrix and rows are separated by a semicolon. There may be ...
1
vote
1answer
42 views

Pumping Lemma for CFL - $ \{ 0^{i} 1^{j} 0^{k} 1^{l} \hspace{0.2cm}| \hspace{0.2cm} i = l \hspace{0.2cm} \land j = k \} $

I was making exercices about the Pumping Lemma for CFL, and I stumbled up on this language: $$ \{ 0^{i} 1^{j} 0^{k} 1^{l} \hspace{0.2cm}| \hspace{0.2cm} i = l \hspace{0.2cm} \land j = k \} $$ I ...
0
votes
0answers
44 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 ...

1
2 3 4 5
27