Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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

0
votes
1answer
6 views

Does reusing variables in Chomsky Normal Form allowed?

I'm not sure if the rules for reusing variables is allowed in CNF. For converting a grammar to CNF, I'm using the rules where new variables and terminals are in the form ...
0
votes
0answers
7 views

Prove that the grammar in Chomsky Normal Form is not Regular [duplicate]

S-> BS|a B-> CB|b C-> SC|c I am stuck with this problem. Can someone please help me to approach this?
0
votes
1answer
28 views

Strings which are not in a language generated by a Grammar

I have the following question and its solution Here T -> XTX since T -> X and X->b S ->XbX since X->a S->aba So,why is option 3 not accepted ?
1
vote
1answer
16 views

PDA of the language where the number of a's are NOT equal to the number of b's

I have this NPDA for language L = {w: num_a(w) == num_b(w)} all loops in q1 ...
0
votes
0answers
16 views

Merging nonterminals of a Context-Free Grammar?

I am reading through a paper on grammatical inference and stumbled upon the following: Given positive example w, we first construct the tabular representation T(w) and the primitive CFG G(T(w)), ...
1
vote
0answers
25 views

How to design a LL(1) grammar for basic regular expression?

I try to design a LL(1) grammar to parse the basic regular expression. Here's the origin grammar.(\| is the escape character, since | is a special character in grammar's pattern). ...
-1
votes
0answers
19 views

$L_4 = \{x: \#_{1}(x) = 2 \cdot \#_{10}(x) \}$ Find CFG given hints [on hold]

Attempt: $S \to A_{00}SA_{11}$ $A_{00} \to 0, 0A_{00}, 0A_{10}$ $A_{01} \to A_{00}1, A_{00}A_{11}, A_{01}1, A_{00}1$ $A_{10} \to 1A_{10}, A_{10}0, 1A_{00}$ $A_{11} \to 1, 1A_{11}, 1A_{01}$ Not ...
0
votes
0answers
21 views

How to modify this CFG to use the conjunction (and) for two sentences?

I wrote the following CFG to parse sentences such as (tom ate pizza), (bill ate rice)...etc.in PROLOG. s(s(NP,VP))-->np(NP),vp(VP). vp(vp(VBD,NP))-->vbd(VBD),np(NP). np(np(NN))-->nn(NN). np(np(NNP))-...
1
vote
1answer
34 views

context free grammar for palindrome: $L_n = \{x \in \Sigma^* | x = ywz, w^R = w, |w| \geq n, |y| = |z| \}$

Let $L_{n} = \{x \in \Sigma^* | x = ywz, w^R = w, |w| \geq n, |y| = |z| \}$ Generate a cfg of $L_n$ For n = 1, 2, 3 Informally, x is in $L_n$ means some palindrome of at least length n is a ...
-1
votes
0answers
24 views

Context-free grammar for all words of the form $a^{3i+1} b^{2j+1}$

How can I create a context-free grammar for the following language? $$ L = \{a^{3i+1} b^{2j+1} \mid i, j \ge 0\}$$
2
votes
0answers
67 views

What is the simplest automaton that can compute the sum of two integers of arbitrary length?

It should be obvious that a Turing machine is capable of computing the sum of two integers. However, what is the simplest automaton that can compute the sum of two integers of arbitrary length? I ...
1
vote
1answer
30 views

Justification for the pumping lemma of context free languages

I understand intuitively why the pumping lemma for regular languages must hold. That is to recognize a infinite string with a finite amount of states you must repeat states and you can "pump" those ...
0
votes
1answer
30 views

How to eliminate ambiguity of the follwing CFG?

Consider the following CFG: $S\to AED | F \\ A \to Aa | a\\ B \to Bb | b\\ C \to Cc | c\\ D \to Dd | d\\ E \to bEc | bc\\ F \to aFd | BC$ The CFG produces $a^*bbb...ccc...d^*$ (equal number of b,...
2
votes
1answer
56 views

Is SAT known to be non-context-free or even non-regular?

We have seen various languages proven to be outside of REG and CFL by corresponding pumping lemmas. Has something similar been done for SAT?
3
votes
1answer
629 views

Does a notion of a context-free complete language exist?

Is there a notion of a context-free complete language (in the analogous sense to a $NP$-complete language)?
1
vote
1answer
11 views

Why can't exhaustive search parsing stop after |w| + 1 derivations?

If my grammar does not have productions of the form $A\rightarrow\lambda$ and $A\rightarrow B$ for some variables $A$ and $B$ then I know that each step in the derivation must involve an increase in ...
1
vote
3answers
67 views

Is the union of 2 non context free languages always non context free?

Let $L_1 = \{a^nb^nc^n\}$ and $L_2 = \{a^ib^jc^k \mid i\ne j\text{ or }j\ne k\}$ (which I think is a non Context free but I am not sure) So, $L_1 \cup L_2$ will give $L_3 = \{a^*b^*c^*\}$ which is a ...
1
vote
1answer
17 views

Describing the Language of a grammar in set theoretic notation where the length of strings need to be remembered

I am not well versed in this topic so please pardon any ambiguous notation. I am trying to describe the language of this grammar in set-theoretic notation. The Grammar is given by: $ S \rightarrow ...
1
vote
1answer
32 views

Designing a context free grammar for a language; When to use the empty string

$L= \{a^{2i}b^{j}vc^{j}(ac)^{i} | i,j \ge 0, v \in \{a,b\}^*\}$ over the alphabet $\Sigma = \{a,b,c\}$ How can a grammar be created from the language without the use of the empty string. Below is my ...
0
votes
0answers
23 views

using pumping lemma to show a language is not CFL--a tricky points for me to clarify

I need feedback on a few things I did come across while proving a language is not CFL. $L=\{a^ib^jc^k | i>j \space and \space j=k\}$. This is not a CFL. And using pumping lemma like the following:...
0
votes
0answers
18 views

Show that {a^ib^jc^k|i>j>k>0} is not a context free language by using pumping lemma [duplicate]

I attempted to try this, but I keep on getting stuck. I was planning on solving it like a pumping lemma question for grammar, but I am not sure. Thank you!
1
vote
4answers
73 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 ...
0
votes
1answer
20 views

Prove or disprove if L is CFL? [duplicate]

Given $L=\{a^ib^jc^k | i\neq j \space and \space j=k\}$. Is this CFL? How do I write CFG for it or prove it with pumping lemma? Thanks.
2
votes
1answer
69 views

How to prove prove $L(G) = \{~w\in\{a,b\}^*~|~\#_aw= \#_bw\}$ for my CFG $G$?

For language $L = \{ x \in \{a,b\}^* \mid \#_a x = \#_b x \}$, I came up with the following CFG: $$S \rightarrow aSbS \mid bSaS \mid \varepsilon.$$ It can be easily shown that it is correct (quick ...
1
vote
1answer
45 views

Is $\{a^mb^nc^{mn}\mid m>n\}$ a context-free language?

Been trying to figure it out for an hour myself and another hour looking around, I cannot find anything with the $c^{mn}$ part. $$L=\{a^mb^nc^{mn}\mid m>n\}$$
0
votes
1answer
44 views

Construct a Deterministic Pushdown Automaton for unequal number of elements

Can anyone help me construct a deterministic PDA for the following language: $$L=\{w\in(a,b)^* \mid \#_a(w)\neq \#_b(w)\}$$ Or can anyone check if the following solution is correct?
0
votes
1answer
39 views

Context-Free Grammar from this language

I'm having difficulties with an exercise in a theoretical CS class. The problem is: let $L_{2}$ be a language defined as follows: after every "a" come atleast two "b" or after every "b" comes atleast ...
1
vote
1answer
16 views

unambiguous context-free languages and complementation

I was considering the following two natural questions about the relationship between unambiguity and complementation for the class of context-free languages: Is the complement of an unambiguous ...
0
votes
1answer
27 views

Robustness of non-context-free proof against trivial manipulation

First, we state here a theorem that is well-known in computability theory: $L=\{xx\mid x\in\Sigma^*\}\notin CFL$ for every fixed $|\Sigma|\geq2$ And, the standard proof is using pumping lemma. At ...
1
vote
1answer
45 views

Is $\{\langle G,x\rangle \mid x\in L(G)\}$ context-free?

Our problem is: Given a context-free grammar $G$ and a string $x$, decide whether $x\in L(G)$. Is this language itself context-free?
1
vote
1answer
54 views

CFG - Ambiguous to Unambiguous

Given the ambiguous CFG : S → 01S1|SS|ϵ I came up with the following CFG which I think is unambiguous: S → 01X | 011X X → 01X1 | ϵ Is my CFG unambiguous and does it represent the same language?
0
votes
1answer
53 views

How many parse trees are there of a given string?

Given a CFG, is there a systematic way to figuring out how many parse trees there are for a certain string? For example, given the grammar: ...
1
vote
1answer
41 views

CFG for language of all palindromes whose number of 1s is divisible by 3

The question is the following: Construct a CFG for $L_2 = \{w ∈ {0, 1}^* \mid w = w^R\text{ and the number of 1’s in $w$ is divisible by 3}\}$. I can construct a CFG for $\{w \in \{0,1\}^* \mid w =...
0
votes
1answer
35 views

What's wrong with this grammar

$L = \{ w : w \in \{a, b\}^* \land |w|_a = |w|_b\}$ where $|w|_a$ means number of $a$ in string $w$. I came up with this grammar: $S \rightarrow aSb \ |\ bSa \ | \ \epsilon .$ Can someone please ...
0
votes
0answers
12 views

How to create a context free grammar for the complement of the following language? [duplicate]

Let $L = \{xcx |x\in\{0,1\}^*\}$, the terminal symbols being $\{0,1,c\}$. The complement would accept the following types of strings: Strings with no c's, i.e. $\{0,1\}^*$ Strings with a single c, ...
3
votes
1answer
46 views

Undecidable problem intersection of two DCFL languages is DCFL?

We have two deterministic pushdown automatas A and B, which languages are deterministic context-free. The problem is to decide if there exists a deterministic pushdown automata, which language is an ...
1
vote
1answer
33 views

Is the Complement of the Language $L=\{wxw^r|w \in (a+b)^+, x \in (a+b) \}$ Context free?

I know that the Context-free languages are not closed under compliment. Given $L=\{wxw^r| w \in(a+b)^+,x \in (a+b)\}$ and this is a Context free language. I think it's compliment will contain words ...
2
votes
3answers
42 views

Given an CFG determine if $\varepsilon \in L(G)$

Given a context free grammar how am I able to determine if $\varepsilon \in L(G)$ ? The only way I thought of is to systematically check if I can derive the empty word from the given grammar. (...
0
votes
1answer
34 views

Use the pumping lemma to prove that the following language is not context free

Can anyone help with the following problem ? Let $B = \{ a^{n}b^{m}c^{m}d^{2n} | n,m ≥ 0 \}$, use the pumping lemma to prove B is not context-free Thanks in advance.
1
vote
1answer
74 views

Is the problem of determining whether a CFG generates a string in the form 0*1* decidable?

Given a grammar $G$, is it decidable whether $G$ generates any string in the form $0^*1^*$? Why? I think it's undecidable but can't find any undecidable problem to reduce it to.
1
vote
1answer
60 views

Prove that every CFL has at least one infinite equivalence class

If we define the Myhill-Nerode relation on a CFL how can i prove that there is at least one infinite equivalence class?
2
votes
1answer
29 views

$a_k$ is $\{L :\exists M$ a pushdown automaton with bounded stack of size $k$ which accept $L\}$ what is the set $\bigcup_1^\infty a_k$?

A related question: How to prove that a bounded pushdown automaton is regular? Well I proved that $a_k$ for each $k$ is the set of all the regular language. Thus $\bigcup_1 ^{\infty} a_k = \bigcup_1 ^...
2
votes
0answers
27 views

How to know a certain grammar is parse-able

Is it possible to parse all kinds of structured data and give them a semantic meaning? For example, C++ is a really complicated language and I could never imagine a parser would be possible for it. ...
2
votes
1answer
52 views

$L$ is a context free language so prefix$(L)$ is also context free language

In case $L$ is context free language. $L_1 \setminus L_2 = \{x\in \Sigma ^* : \exists y\in L_2$ s.t $xy\in L_1 \}$ when $L_2$ is regular, is a context free language, thus using $L_1 = L$ ,$L_2 = \...
3
votes
1answer
71 views

Are the languages $\{w\in \{a,b\}^* : \#_a(w) > \#_b(w) \}$ and $\{w\in \{a,b\}^* : \#_a(w) \neq \#_b(w) \}$ context free?

So at the beginning I was aiming at $L_{a\neq b} = \{w\in \{a,b\}^* : \#_a(w) \neq \#_b(w) \}$. But figured out that is would be better to first deal with: $L_{a>b} = \{w\in \{a,b\}^* : \#_a(w) &...
0
votes
0answers
29 views

Difference between n-bit Ripple carry adder and a cascade of k n-bit adders?

What is the basic difference between the two adders considering that they both almost do the same thing.
1
vote
1answer
31 views

Words generated by CFG whose parse tree contain even number of $X$

Let $G$ be a context-free grammar with set of terminals $A$. Let $X$ be a non-terminal in $G$. Is the language of words over the alphabet $A$ with a syntax tree in which the non-terminal $X$ appears ...
3
votes
2answers
33 views

Question about mapping reducibility

I am working on an assignment where one of the sub questions is: Let $A$ and $B$ be languages. Suppose $A$ is context free and $A ≤_m B$, which means that there is a computable function $f\colon \...
2
votes
1answer
58 views

Context formal language recognizing even number of 0's and odd number of 1's

I have an assignment, it's asked to write a context free grammar recognising the language $L=\{ w \mid w\text{ has an even number of }0\text{s and an odd number of }1\text{s}\}$, over the alphabet $\{...
0
votes
1answer
53 views

Does a pushdown automata exists for the following language?

I have came across a question stating that language $L = a^n b^n c^{2n}$ is not a context free language and hence, no PDA can be constructed for it. But what I am wondering is that, if I add another ...