The context-free-grammar tag has no wiki summary.
1
vote
0answers
27 views
Is this language context-free?
$L=\{ xcycz : x,y,z \in \{a,b\}^* \wedge xy, \ yz - \text{palindromes} \}$
Is $L$ context free language?
0
votes
0answers
34 views
Write a grammar for language $a^ib^jc^k$
Problem:
Write a grammar for a language:
$$L=\{ a^ib^jc^k : j=2(i+k)+1 \}$$
My solution:
$S \rightarrow AbB$
$A \rightarrow \epsilon$
$A \rightarrow aAbb$
$B \rightarrow \epsilon$
$B ...
1
vote
0answers
44 views
Proof that equal-length-concatenation is a context-free language?
If A and B are languages, define A⋄B={xy | x ∈ A and y ∈ B and |x|=|y|}. For example, if A = {00, 101, 111} and B= {1, 11, 00110}, we would have A⋄B={0011}.
Show that if A and B are regular, ...
0
votes
1answer
32 views
Is language, made of the first half of the words from context-free language, context-free?
L is context-free language. Then we make new language L'={x|$\exists$y xy∈L,|x|=|y|}.
Is L' context-free or not always?
I'm stuck on this problem. I suppose that there are examples when L' isn't ...
2
votes
3answers
47 views
Find push down automata and context free grammar
I have the following language:
$$
L = \{a^nb^{2n+1} \mid n \ge 0\}
$$
I must find the push down automaton and a context free grammar for the language.
For the push down I have no idea how to ...
1
vote
1answer
32 views
Context Free Grammar Equal Lengths
Consider the language L = {x#y is in {0,1}* where |x| = |y|}
Would this CFG be a sufficient definition of the language L?
S->0S0 | 0S1 | 1S0 | 1S1 | #
Thanks.
1
vote
0answers
17 views
CNF: Recursion in CFGs
How can I deal with recursive terminals in CFG when converting it to CNF? For example,
S -> MN
M -> AM | A
N -> BN | B
A -> a
B -> b
How can I reduce terminals M and N?
1
vote
1answer
29 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
32 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
60 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
46 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
29 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
15 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
27 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
38 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
37 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
45 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
24 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
42 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
67 views
How to construct a context free grammar $G$ such that $L(G) = \{ a^i b^j a^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
58 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
72 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
54 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
40 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
53 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
35 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
95 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
83 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
34 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
54 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
54 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
47 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
50 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
42 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
58 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
40 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
64 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
137 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
50 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
59 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
78 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
42 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
76 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
117 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
311 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
82 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
65 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
135 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.
