The context-free-grammar tag has no wiki summary.
1
vote
1answer
23 views
Context-Free Grammar construction when order isn't specified
I'm having trouble constructing a grammar for
L={wϵ{a,b}|na(w)≠nb(w)}
So I need to construct a grammar for the language wherein the number of a's does not equal the number of b's. The farthest ...
1
vote
1answer
28 views
CFG for language
I can't find CFG for this language.
$N = \{w ∈ \{0, 1\}^* \mid \text{w contains more } 1\text{s than }0 \text{s}\}$
Basically, it is much easier when order is set (for example, $1$s come after $0$s) ...
1
vote
2answers
36 views
Are regular languages necessarily deterministic context-free languages?
The original problem
Suppose M is DCFL (Deterministic Context Free Language) and N is a regular language. Answer the following questions and justify your answers.
a) Is M-N necessarily context-free?
...
4
votes
1answer
40 views
Is any formal language with given restriction context free?
Consider formal language $L$ in which each word has non-trivial period (non empty prefix that is also a suffix) over finite alphabet. Is $L$ context free?
I think that $L$ can be non context ...
1
vote
1answer
26 views
Are these two context free grammars equivalent?
Let Σ = {a,b}. A CFG for the language {a^nb^m | n > 2m} can be written as:
S-->aaSb
S-->A
A-->aA
A-->a
Would it be equivalent to write this CFG as:
...
0
votes
0answers
13 views
Precedence Relation Table and Bottom-Up parsing
I have following rules:
E->E+T|T
T->T*P|P
P->(E)|V
I need to create a precedence relation table. It is said that it can be accomplished Wirth-Weber ...
0
votes
0answers
25 views
Weak Precedence Grammar and Bottom-up parsing
I am studying parsing, i.e. bottom-up parsing. it is said that there some rules which are used by weak precedence grammar. What does weak precedence grammar mean? What about precedence relation?
Any ...
0
votes
1answer
33 views
Homorphism and Context Free Grammar
Could you explain me concept of homomorphisms and usage of it to the following problem which requires to prove that $L$ is not context-free?
$$L=\{ba^{n-1}ba^nb:n\ge 1\}$$
Thanks
0
votes
1answer
32 views
Pumping lemma and CFG
I am solving problem in pumping lemma for context-free languages. I want to ask a hint for the following problem
$$L=\big\{www:w\in\{a,b\}^*\big\}$$
Thanks
0
votes
1answer
38 views
Pumping lemma for CFG
it is another my question. Can you give me hint to solve the following problem?
Prove that $L=\left\{a^{n^2}:n\ge 0\right\}$ is not a context-free language?
Thanks!
0
votes
1answer
23 views
CFG and closure properties
I am solving one problem and I urgently need a hint to solve one problem:
Use closure under union to show that the following language is context-free
$$\left\{a^mb^nc^pd^q : n=q,\ \text{or}\;\ ...
1
vote
1answer
39 views
Which one of these language Context free?
Which one of the following languages is CFL and what is the grammar for it? Can we use pumping lemma for the not CFL?
\begin{align*}
L_1 &= \{a^mb^ma^n \mid m,n \geq 0\}\\
L_2 &= \{a^mb^ma^n ...
1
vote
1answer
54 views
How to construct a context free grammar $G$ such that $L(G) = \{ 0^i 1^j 0^k| j \gt i+k\} $?
How to construct a context free grammar $G$ such that $L(G) = \{ a^i b^j a^k| j \gt i+k\} $?
My attempt:
$G_1 = (\{ S,A,B\}, \{a,b\},P,S)$ where $P$ consists of:
$$ S\to AbBC $$
$$A \to ...
1
vote
1answer
44 views
How to construct a context free grammar $G$ such that $L(G) = \{ a^i b^j c^k| j \gt i+k\} $?
How to construct a context free grammar $G$ such that $L(G) = \{ a^i b^j c^k| j \gt i+k\} $?
I don't have much idea how to approach this one. Could some help me to understand how to approach these ...
0
votes
1answer
57 views
Find context free grammar and prove its correctness
Find context free grammar for a given language and prove its correctness:
a) $\left\{ a^ib^ja^k : i\neq j \ \vee \ j\neq k \right\}$
b) $\left\{ w\in \left\{a,b\right\}^* : \#_a(w)=2 ...
0
votes
1answer
51 views
Context free grammar to language
Suppose we have $G(V,Σ, R, S)$ where
$$\begin{array}{ll}
V & = \{a,b,A,B,S\}\\
Σ & = \{a,b\}\\
R &= \left\{ \begin{array}{rl} S &→ abA,\\
S&→B,\\
S&→baB,\\
S&→e,\\
...
0
votes
1answer
36 views
Context Free Grammar for $L = \{0^n w 1^n \mid n \ge 0, w \in \{0, 1\}^*\}$
Title says it all. I'm trying to make sure I have the correct CFG for $L$ before I start converting it to GNF. I don't want to post my idea yet, as I don't want it to influence any of the replies.
...
0
votes
0answers
50 views
Pumping Lemma length, $K$ for context-free language
Please help me understand, and if possible, tips, to determine a pumping length $K$.
Suppose I have the example :
Let $G$ be a Context-Free-Grammar with a set of variables $\{S,A,B,T\}$, set of ...
0
votes
0answers
33 views
Chomsky Normal Form solution for a problem
Here is my attempt at CNF,
Original:
$$
\begin{align*}
S &\to 1 A \mid O B \\
A &\to O B O \mid 1 0 \mid \epsilon \\
B &\to A 1 A \mid 0 1
\end{align*}
$$
CNF:
$$
\begin{align*}
S ...
2
votes
0answers
21 views
defining relationship between geometric entities (features)
I have different features located on a plane (2D); I want to define this structure mathematically in a way to represent their relations. Some of features are aligned in horizontally, vertically or ...
2
votes
1answer
88 views
Show that this language cannot be accepted by a deterministic push-down automaton [duplicate]
How do you show that there exists no DPDA that accepts $ L = \{0^n1^n \} \cup \{ 0^n1^{2n}\}$ ?
1
vote
1answer
73 views
Finding a context-free grammar for $a^i b^j : 2i < j$
So I have a question:
Give a CFG for $a^i b^j : 2i < j$.
And this is my approach:
$$S \to AB$$
$$A \to aAb | e$$
$$B \to b | bB$$
Thanks, a confirmation, or correction, along with how you ...
2
votes
1answer
33 views
My approach to a CFG
this site has been of great help, and I am certainly indebted to your assistance.
I was solving a question, $a^i b^j$ where $0\le i\le j\le 2\cdot i$
And here is my approach:
$S\to aSb \;|\; aSbb ...
2
votes
1answer
49 views
Constructing PDA with either one state or two states
If $L$ is a context-free language and $\epsilon \notin L $, how do you show that there exists a PDA that accepts the language by final state such that it has not more than two states and makes no ...
1
vote
1answer
46 views
$w$ such that it contains at least 3 ones, is my approach to the CFG right?
So I was trying to solve the CFG,
$$\{w \in (0,1)^* \mid w \text{ contains at least three 1's}\}$$
My approach:
I decided that a string can begin with a $0$, end with a $0$, it may begin with a ...
1
vote
1answer
43 views
A CFG for the language $\{ O^i 1^j 2^k 3^l : i=k, j>1 , l>0 \}$: Is my approach correct?
I am trying to construct a CFG for the CFL $\{ O^i 1^j 2^k 3^l : i=k, j>1 , l>0 \}$.
When given $i=2$, $k=2$, $j=2$, and $l=1$, this yields the string $0011223$.
My approach:
$$\begin{align}
S ...
0
votes
1answer
29 views
Infinite context free subset
Disprove that:
Given an infinite recursive language $L$, there exists an context free, infinite subset $A$ of $L$.
This was asked in the exam. Any hint/partial solution?
3
votes
2answers
48 views
Is my context free grammar here correct?
So in preparation for an interview, I have been revising and studying by solving some CFGs, and here is a question, which I solved, but I feel like I haven't solved it right, given its boundary ...
1
vote
1answer
41 views
Decidability Turing Machine Problem
$L=\{G|G$ is a context free grammar over ${a,b}$ and $L\{G\}$ contains
at least one string $w$ such that the number of $a$'s in $w$ is a
multiple of $5\}$
Show that L is decidable by ...
2
votes
2answers
57 views
Context free grammar construction
My problem with CFG is, I am to generally create ones but once they have requirements such as:
$$\{a^m b^n: m\le n\le 2m\}$$
I have no clue where to begin, and how to approach it. I was wondering if ...
2
votes
1answer
38 views
Proving non CFL with pumping lemma
I can't seem to figure out how to prove this as not a CFL:
$$\left\{x^{a}y^{b}\mid a=kb\space\text{for some positive integer k}\right\}$$
I've tried a bunch of "s"'s to pump such as $a^{2p}b^{p}$ ...
2
votes
2answers
61 views
Describe a PDA that accepts all strings over $\{a, b\}$ that have as many $a$’s as $b$’s.
I'm having my exam in few days and I would like help with this
Describe a PDA that accepts all strings over $\{ a, b \}$ that have as many $a$’s as $b$’s.
4
votes
2answers
118 views
Push down automata problem
Informally describe the Nondeterministic PDA that generates:
$$\{x\#y\ \mid x,y\in\{a,b\}^{*}\text{and}\space x\ne y\}$$
My initial plan was to use nondeterminism to go through each character before ...
3
votes
1answer
46 views
Context free language problem
I'm trying to find an unambiguous context free language for the ambiguous language:
$$S\rightarrow AB$$
$$A\rightarrow Ba| b$$
$$B \rightarrow aA|b$$
I understand the language makes up of strings ...
3
votes
1answer
58 views
Does the Halting Problem apply when evaluating programs that are regular languages?
Here is my understanding of the Halting Problem: It is impossible to write a program H that can determine for any arbitrary program ...
2
votes
2answers
73 views
Is this proof using the pumping lemma correct?
I have this proof and it goes like this:
We have a language $L = \{\text{w element of } \{0,1\}^* \mid w = (00)^n1^m \text{ for } n > m \}$.
Then, the following proof is given:
There is a $p$ ...
0
votes
1answer
40 views
Showing the following language is not contex free
I need to show the following language is not context free via the Pumping Lemma.
$$L = \{0^n\#0^{2n}\#0^{3n}\mid n \ge 0 \}$$
I was wondering if someone can help explain how to begin such a proof. ...
5
votes
4answers
74 views
Shortest string possible
I was at an interview, and I was asked to give the shortest string generated given this context free grammar. I did not review in years, so I think I got it wrong. What is the answer so I know it for ...
3
votes
1answer
112 views
Context Free Language? Proving through grammar?
I need help solving this question:
Is $L = \{ w \in \{a,b,c\}^* \mid n_a(w) = n_b(w) = 2n_c(w)\}$ a context-free language?
That is the number of $a$'s equal the number of $b$'s equal twice the ...
0
votes
2answers
274 views
Pumping Lemma to show that a language is not Context Free [duplicate]
I am trying to use the Pumping Lemma to prove that the following language is not context free:
$$\{0^n\mid \text{$n$ is prime}\}$$
I am having a really difficult time with Pumping Lemma. Up until ...
1
vote
2answers
75 views
Is L a context free langauge? context-free grammar?
Is $L = \{ a^{(i)} b^{(i)} c^{(j)} \mid i \le j\}$ a context-free language?
Would i just create a context free grammar for this?
2
votes
1answer
61 views
Is $L = \{a^{n+2} b^n | n \ge 0\}$ context free or regular?
Is the language $L = \{ a^{n+2} b^n | n \ge 0 \}$ context free? If so, what is a context free grammar for it? If it is regular, what is a right linear grammar for it?
0
votes
1answer
120 views
An infinite context free language can be split into two infinite regular languages
Prove or disprove
Let $L$ be an infinite context free language. Show that there exists a regular language $R$ such that $ L \cap R $ and $L \cap \overline{R} $ are infinite and regular.
4
votes
1answer
43 views
Does the following transformation preserve context-freeness?
I encountered this problem involving manipulating a context-free language. Let $L$ be a context-free language. Define $L^{\#} = \{ x : x^i \in L$ for every $i=0,1,2,...\}$. Is $L^{\#}$ always ...
0
votes
1answer
84 views
Find grammar for given language
I want to practice finding grammars for given languages. Unfortunately after solving some easy examples I found out that I completely don't know how to approach these more ambitious. For example when ...
1
vote
0answers
72 views
If there is an infinite loop in a context-free grammar, is the resulting language context-free?
Suppose I have the following context-free grammar:
$ S = A \\ A = aA
$
Will the resulting language be context-free?
If it is, this would also mean a Turing machine should be able to produce it, ...
0
votes
1answer
138 views
Determining Ambiguity in Context Free Grammars
What are some common ways to determine if a grammar is ambiguous or not? What are some common attributes that ambiguous grammars have?
For example, consider the following Grammar G:
$S \rightarrow ...
1
vote
1answer
91 views
Proof of the pumping lemma for Context-Free Languages
I have a doubt concerning the proof of the pumping lemma for context-free languages. The pumping lemma for context-free languages is stated as follows:
If $A$ is a context-free language, then ...
2
votes
1answer
295 views
Converting to Chomsky Normal Form
I am trying to learn how to convert any context free grammar to Chomsky Normal Form. In the example below, I tried to apply Chomsky Normal Form logic, to result in a grammar, where every symbol either ...
1
vote
0answers
33 views
Non context-free languages closed under reverse
Is this sentence true or false? I'll be glad for some explaination
L is not context-free, then its reverse is also not context-free
Thanks in advance
