All Questions

Filter by
Sorted by
Tagged with
-1
votes
2answers
58 views

Context-free grammars for two languages

How do I write context-free grammars for the following languages? $B_2 = \{0^n1^n \mid n > 0\} \cup \{0^n1^{2n} \mid n > 0\}$ $B_3 = \{a^nb^mc^k \mid k = n+m\}$ Can someone help me? I'm not ...
0
votes
0answers
14 views

Non-context free languages with word degree [duplicate]

I have stumbled across these 2 problems $L_1= \{\alpha \mid w \in \{a,b\}^* | \alpha $ has exactly 2 b's$\} $ ,prove that $L =\{ \alpha^n | \alpha ∈ L_1 ,n \ge 0 \}$ is not context free Given : $...
5
votes
2answers
1k views

Why is the start symbol “not allowed” on the right hand side in Chomsky normal form?

I had a question regarding CNF (Chomsky normal form) in formal language theory. I noticed that a lot of authors (including my own professor, and the Wikipedia page for CNF) frown upon or don't allow ...
0
votes
1answer
85 views

Context-free grammar from language

I'm trying to come up with a context-free grammar for the following language: $$L = \{a^mb^nc^{m+n}\mid 0 \le n \le m\}$$ My thinking is that i can rewrite this to $$L = \{a^mb^nc^nc^m\mid 0 \le n \...
9
votes
2answers
11k views

Why are CFLs not closed under intersection?

I'm struggling with understanding how context free languages can be closed under union but are not closed under intersection. I was wondering if there was a simple proof or example demonstrating that ...
0
votes
0answers
103 views

Is $\{ a^i b^j c^k : i + 1000\ < j + 100 < k \}$ context-free?

I have this language: $$ L = \{ a^i b^j c^k : i + 1000\ < j + 100 < k \}, $$ and what I believe is that we can't prove with the Pumping Lemma that it is not context-free, because we would ...
0
votes
0answers
15 views

How do we determine p (pumping length) in pumping lemma for CFL? [duplicate]

This has been confusing me for a while, how do we exactly choose the pumping length when we want to prove whether a language is CFL or not. For example, when we want to prove that {ww, w: {0,1}* } why ...
1
vote
1answer
1k views

Is the union of two non-regular context-free languages always non-regular?

I had this question in my HW: Prove of disprove: If $L_1$ and $L_2$ are non-regular context free languages then $L_1 ∪ L_2$ is not regular. My intuition is that it is wrong. I thought about the ...
1
vote
2answers
337 views

Is it possible to create a CFG with succesive palindromes?

In one of my homework I am requested to find a Context-free-grammar (CFG) and a push down automaton (PDA) for the following language: $L = \{x_1\#x_2\#...\#x_k | k \geq 2, \text{ each } x_i \in \{a, ...
1
vote
1answer
69 views

Problem with forming a context-free grammar describing a language

I've been trying for hours to figure out, how to form a CFG describing this language $L$: $$L=\{ w\in\{a,b\}^* \mid w\text{ is of the form }a^nxb^{n+2}\text{, where }x\text{ is a string of length }3\...
1
vote
1answer
697 views

Is the set of all Context free languages a Context sensitive Language? ( can we build a LBA that decides whether a given language is CFL or not?)

What i mean is that can we code each CFL ( the same way we code each turing machine in the Universal Turing Machine ) and build a Linear bounded Automata in such a way that for each input ( which is a ...
8
votes
2answers
311 views

Is {a^n (a+b)^n | n>0} a Deterministic CFL?

$L = \{ a^n (a+b)^n | n>0\}$ A book I'm reading says it is, but considering we can't know where the second part gonna start, and it might start with a as well, then how can we accept this using ...
0
votes
1answer
270 views

Pushdown Automaton for $L = \{ w_1 w_2 : |w_1| =|w_2| , w_1 \neq w_2 \} $

So i know that $L =$ { $ {w_1 w_2 : |w_1| =|w_2| , w_1 \neq w_2} $ } is a CFL, but i cannot make a PDA for it because it doesn't make any sense to me why this is CFL i even know the grammar for it ...
0
votes
1answer
267 views

Show that the Pumping Lemma for CFLs is not powerful enough to prove that the language L = {aibjck |i ≠j ≠ k ≠ i } is not context free

Show that the Pumping Lemma for CFLs is not powerful enough to prove that the language $L = \{a^ib^jc^k \mid i ≠j ≠ k ≠ i \}$ is not context free. From my understanding, we want to prove that all 3 ...
1
vote
1answer
642 views

Prove that the language $L_1 = \{a^ib^{2i}c^j \;|\; i,j ≥ 0\}$ is context-free

Prove that the language $L_1 = \{a^ib^{2i}c^j \;|\; i,j ≥ 0\}$ is context-free. I have a grammar like this but there are some strings that are not be able to be generated $$\begin{align} S &\to ...
6
votes
2answers
139 views

Can the regular image of a context-free language be undecidable?

I just need to know the truth or falsity of a simple statement. Let $L_1$ be a context-free language over an alphabet which contains some number of characters $\Sigma$, as well as a single, special ...
2
votes
0answers
87 views

Looking for a subclass of deterministic context-free languages, other than the subclass of regular languages

Let $X=\{x_1,\ldots,x_n\}$ be a finite set of alphabet and $X^\ast$ denote the set of all words (including empty word) over $X$. Clearly, $X^\ast$ is a regular language. Is there a subclass, say $C$, ...
1
vote
2answers
159 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 ...
4
votes
1answer
828 views

Basic doubt in converting PDA to DPDA

This is the PDA to accept strings with equal number of $a$'s and $b$'s. The $\epsilon$ transition in the first state is causing nondeterminism. When we have input a with Z at the bottom of the stack, ...
1
vote
2answers
76 views

Can a DPDA decide if two letters appear the same number of times mod 5?

$ L = \{ w ∈\{0,1\}^* \mid |w|_0 = |w|_1 \mod 5 \}$ So i tried figuring out why this is CFL and whether its DCFL or not but i couldn't come up with any PDA! I'm studying for my exam and this ...
2
votes
0answers
95 views

How to prove that a language created from a context-free gramar's left side is regular(or left-linear)?

Given a context-free grammar $G$, let $\longrightarrow_G$ be the (one-step) rightmost derivation relation, and $\longrightarrow^*_G$ its reflexive and transitive closure. Let $S$ be the start symbol ...
0
votes
1answer
40 views

Is the language $L = \{a^pb^q \ | \ p \ge 1, \ q \ge 1, \ p \ge q^2 \ or \ q \ge p^2\}$ context free? [duplicate]

Is the language $L = \{a^pb^q \ | \ p \ge 1, \ q \ge 1, \ p \ge q^2 \ or \ q \ge p^2\}$ context free? I should probably use Ogden's lemma, but I don't know how to do that in this case.
2
votes
3answers
987 views

What parts of a programming language can't be defined using Regular Expressions?

I'm trying to understand how the syntax of some programming language is defined. I know that there are some parts of the syntax of programming languages that can't be defined using regular ...
2
votes
1answer
352 views

Is the language given by a context-free grammar always context-free?

Consider the language generated by the following grammar: $S \to aSBb \mid \epsilon$ $B \to aB \mid bB \mid \epsilon$ Is the above language context-free? The above language looks like $\{ w \in (...
2
votes
0answers
592 views

Is the complement of $L = \{a^nb^mc^p \, n= m= p\}$ context free language?

Is the complement of $L = \{a^nb^mc^p \ , n= m= p\}$ a context free language. I believe that we can write $L^{'} \ as \ L1 \cup L2$ where $L1=(a^*b^*c^*){'} \ $ $L2={{a^nb^mc^p \ m\ne n \ or \ n\...
2
votes
1answer
85 views

Proving $L = \{ w : w \neq w^R \}$ over $\Sigma = \{0,1\}$ is CFL

I'm trying to prove $L = \{ w : w \neq w^R \}$ over $\Sigma = \{0,1\}$ is CFL. Define $G = ({S,T}, \Sigma, R, S)$ where $R = S \to 0S0|1S1|0T1|1T0, \; T \to 0T|1T|\varepsilon$. Now I want to show ...
0
votes
1answer
125 views

Prove or disprove: Complement of language $L=\left\{baba^2ba^3b…ba^{n-1}ba^nb \, | \, n \geq 1\right\}$ is context-free

Prove or disprove: Complement of language $L=\left\{baba^2ba^3b...ba^{n-1}ba^nb \, | \, n \geq 1\right\}$ is context-free. I'm not quite sure how this is done. I would first try to find out ...
2
votes
0answers
623 views

Understanding definitions of Deterministic Context Free Grammar and Deterministic Pushdown Automaata

I read following here: Unambiguous grammars do not always generate a DCFL. Example: For example, the language of even-length palindromes on the alphabet of 0 and 1 has the unambiguous context-...
4
votes
2answers
1k views

How can the intersection of CFLs and REGs be CFL if REG is a proper subset of CFL?

Intersection of CFL and regular is always CFL. But according to Chomsky hierarchy diagram, regular languages lie completely inside CFL. So, as regular set is completely inside CFL set, their ...
1
vote
2answers
646 views

Prove grammars with long derivations generate infinite languages

Suppose $G$ is a CNF (Chomsky normal form ) grammar which has $v$ variables. ($|V| = v$) If there is a string that $G$ derivatives in more than $2^v$ steps, prove that $L(G)$ is infinite. Any ...
0
votes
2answers
175 views

Removing epsilon transition from the grammar. What's the difference between accepting languages?

I want to remove the epsilon transition from following grammar: \begin{eqnarray} S & \rightarrow & A | B \\ A & \rightarrow & \epsilon \\ B & \rightarrow & aBa \\ B & \...
0
votes
0answers
194 views

How to show that a language is strictly context sensitive

During a class, we was asked how to prove that a language L is strictly context-sensitive. In particular, we have to prove that $L = \{a^nb^nc^n \mid n > 0\}$ Could you help me to find the ...
2
votes
1answer
1k views

Unambiguous grammar for regular expressions

How to define a non ambiguous grammar for regular expressions on the $\Sigma = \{a,b\}$ alphabet? Given that: If $\Theta = \{+, ^*, (,),\cdot, \emptyset\}$ is a set of symbols A regular expression ...
0
votes
1answer
608 views

Pumping lemma for context-free languages - Am I doing it right? [closed]

I have an exam coming up in three days, and there's a thing that I really need to be able to completely understand - that is, of-course, pumping lemmas for CFL. I know how to do prove that a regular ...
1
vote
1answer
348 views

Are linear languages always unambiguous?

Deterministic Context free languages are always unambiguous. Now DCFL are a subset of linear languages. Are there any linear languages which are inherently ambiguous?
5
votes
1answer
619 views

Prove or disprove that the following language is context-free

Hi guys I was given this question: Prove or disprove that the following language is context-free: $$ L = \{ \alpha 2 \beta : \alpha,\beta \in 1(0+1)^*, [\alpha]_2 < [\beta]_2 \} $$ where $[x]_2$ ...
0
votes
1answer
313 views

Infinite Union of Recursive language

Question Is Infinite Union of Recursive language is Recursive? I know it is already posted here, but the i am not getting answer also i want to know if my approach is correct. My Approach/Doubt $\...
3
votes
3answers
4k views

Why are DCFL not closed under concatenation or Union whereas CFL is?

I understand that DCFL they are not closed under concatenation or Union. As without non determinism, PDA cannot decide when to jump to the next one in case of concatenation and without epsilon moves ...
1
vote
1answer
105 views

Find a CFG for univocalic words

I'm trying to figure out how to create a CFG for univocalic words... Univocalic words are words that have only one the same vowel letter throughout the word Example: September, Anna Would ...
1
vote
1answer
408 views

prove that l={w ∈ {0, 1}*: n0(w) ≠ n1(w)} is a non regular language?

I tried doing this, but kept failing to prove. I know how to prove that the language is nonregular when n0(w) = n1(w). The following is the proof for n0(w) = n1(w) using pumping lemma: ...
0
votes
1answer
555 views

Find the Context Free Grammar

Let $\Sigma = \{a, b\}$. For each of the following languages, find a grammar that generates it. (a) $L_1 = \{a^n b^m : n\geq 0, m>n\}$ (b) $L_1^3$ (C) $L_1^*$ I know the grammar for the ...
3
votes
0answers
27 views

How to model grammar ambiguity

Say you have a (context-free) grammar, and you wish to mathematically model the magnitude of the ambiguity possible under this grammar, across the space of all possible** input strings. Practically, ...
1
vote
0answers
61 views

Pumping lemma for CFL language

Let $L$={ $\alpha$ in {$a,b$}* | $\alpha$ has exactly two symbols b } .Prove that $L'$ = { $\alpha^n$ | $\alpha$ in $L$ ,$n \ge$0} is not context-free.I was thinking to prove it that way: Since $a^nba^...
0
votes
0answers
24 views

Operation on languages results in CFL

For every two languages $L_{1}$ and $L_{2}$ over the alphabet $\{ a,b,c,d \}$, we define the language $$L_{1} \operatorname{op} L_{2} = \{ \alpha\beta \mid \text{$\alpha \in L_{1}$ and $\beta \in L_{...
0
votes
1answer
156 views

Proving this language is not context free using the pumping lemma

I am trying to prove why the below language is not context free. Note: this should be carried out by applying the pumping lemma for context free languages. To prove something with the pumping lemma, ...
1
vote
1answer
1k views

Can Chomsky Normal Form have more than one terminal?

In formal language theory, a context-free grammar G is said to be in Chomsky normal form if $$ S → A B$$ $$ A → a $$ $$S → ε $$ My question is that if $B$ in the the form of $$ B → abcd $$ where $...
0
votes
0answers
27 views

Is this language a context-free language? [duplicate]

I'm currently trying to figure out whether this language is context-free using the pumping lemma. $\qquad L = \{ v_1 v_2 v_1 v_2 \mid v_1 \in \{a, b\}^*, v_2 \in \{a, c\}^* \}$ I'm having trouble ...
0
votes
0answers
49 views

Interpreting the way we choose partitions in the pumping lemma for CFLs

This question is referring to the Pumping Lemma for CFLs, namely: If $L$ is a CFL, there is a pumping length $p$ such that any string $z \in L$ of length $\geq p$ can be written as $z = uxwyz$, ...
0
votes
1answer
169 views

Check if given language is CFL

Assume language $L$ as follow:- $$ L = \{ a^n b^x c^m d^y | (n=m) \lor (x=y)\} $$ Is it possible to design DPDA/NPDA for this? I know if the condition would have been "and" then it is not possible. ...
0
votes
1answer
2k views

PDA or CFG for language $L= \{a^ib^j | 2i \leq 2j \leq 3i, i>0\}$

Can someone help with this $L= \{a^ib^j | 2i \leq 2j \leq 3i, i>0\}$

1
3 4
5
6 7
14