Questions about the set of languages (equivalently) described by context-free grammars or accepted by (non-deterministic) pushdown automata.
1
vote
1answer
17 views
How to construct a context free grammar for $a^i b^j c^k$ with $j \gt i+k$?
How to construct a context free grammar $G$ such that $L(G) = \{ a^i b^j c^k \mid j \gt i+k\} $?
I don't have much idea how to approach this one. Could some help me to understand how to approach ...
2
votes
1answer
28 views
Prove that context free languages are not closed under swapping prefixes and suffixes
Prove that context free languages aren't closed under this operation: $ A(L) = \{ zyx \mid x,y,z \in \{0,1 \}^*, xyz \in L \} $
Obviously, we need to find a context free language $L$ such that $A(L)$ ...
1
vote
2answers
35 views
Converting CFG to PDA
I have the following CFG,
$S \rightarrow CB$
$C \rightarrow aCa \text{ }|\text{ } bCb \text{ }|\text{ } \text{#}B$
$B \rightarrow AB \text{ }|\text{ } \varepsilon$
$A \rightarrow a\text{ }|\text{ }b$
...
1
vote
0answers
44 views
Is the language $L = \{ a^ib^j \mid i\ \nmid\ j \ \} $ context free?
Is the language $L = \{ a^ib^j \mid i\ \nmid\ j \ \} $ context free ?
If we fix $n \in N$ then we know that the language $L = \{ a^ib^j \mid \ \forall \ 1 \le k \le n \ , \ \ j\neq ki \} $ is ...
1
vote
1answer
21 views
Is the intersection of two context free languages recursively enumerable?
I read a quotation attributed to Sheila Greibach that says that the intersection of two context free grammars is recursively enumerable.
I could not, however, find a citation for this quotation (and ...
1
vote
1answer
28 views
Questions about an answer to a pumping lemma question for CFLs
In the answer to this question, I'm not understanding how the string is derived for a given $l$.
For example,
Case 1: $vx = a^i$ where $i > 0$. Choose $l = 2$ to get $a^{n+i} b^{n+1} c^{n+1} ...
2
votes
0answers
29 views
The grammar of the GeoQuery language
GeoQuery is a dataset used for benchmarking semantic parsers. It contains 880 queries about USA geography. The queries are in Prolog format, for example:
...
3
votes
1answer
49 views
Are permutations of context-free languages context-free?
Given a context-free language $L$, define the language $p(L)$ as containing all permutations of strings in $L$ (i.e. all strings in $L$ such that the order of symbols is not important). Is $p(L)$ ...
2
votes
2answers
61 views
Designing a PDA w/o $\epsilon$-moves and $\leq 2$ states to accept an $\epsilon$-free CFL by final state
I understand that any CFL can be accepted by a PDA by final state or empty store but I have been rather stumped by this question.
The question states that the PDA has at most 2 states. Clearly 1 will ...
0
votes
2answers
44 views
Proving $\{xx^R \mid x\in L_1, x^R\in L_2\}$ is context-free
I have this problem:
Let $L_1$ and $L_2$ be two regular languages. Show that $L_3 = \{xx^r : x \in L_1, x^r \in L_2 \}$ is a context-free language.
I am unsure how to prove that some language ...
8
votes
1answer
173 views
Is the language $\{0^n 1^m \mid n \text{ and } m \text{ are co-prime}\}$ context-free?
Is the language $ L = \{0^n 1^m \mid n \text{ and } m \text{ are co-prime}\}$ context-free ?
I guess that it's not context free because it seems too complicated for a PDA to decided whether 2 numbers ...
0
votes
0answers
13 views
Pumping Lemma on CFL Problem [duplicate]
I have laid out the various cases that would make this not a context free language already and proved all but one for this set:
\begin{equation}
A = \{a^f b^g \mid f = g^2\}
\end{equation}
...
3
votes
1answer
61 views
How to find the pumping length of a context-free language?
Please help me understand, and if possible, tips, to determine a pumping length $p$.
Suppose I have the example :
Let $G$ be a Context-Free-Grammar with a set of variables $\{S,A,B,C\}$, set of ...
0
votes
1answer
37 views
Convert CFG to PDA
Is there any set of rules or methods to convert any context free grammar to a push down automata?
I already found some slides online but I wasn't able to understand them.
In slide 10 he speaks ...
0
votes
0answers
25 views
Is this Chomsky Normal form correct? [closed]
Here is my approach, am I right?
Chomsky Normal Form solution for a problem
Here is my attempt at CNF,
...
4
votes
1answer
38 views
Closure under intersection of context free binary trees
Some sets of ordered binary trees can be represented as a CFG with rules of the form
A -> aBC
A -> b
Where A,B,C are ...
6
votes
1answer
91 views
Are context-free languages in $a^*b^*$ closed under complement?
The context-free languages are not closed under complement, we know that.
As far as I understand, context-free languages that are a subset of $a^*b^*$ for some letters $a,b$ are closed under ...
4
votes
2answers
96 views
Why is the following language not context-free?
$L = \{a^n b^m | m \not= n^2 \}$
I guess I need to use Pumping Lemma for CFL in order to prove this. But I'm stuck.
Assuming that $ a^n b^m = uvxyz$, we know that $v$ or $y$ can not have both $a$ ...
0
votes
1answer
30 views
CFG for $\{a^i b^j : 2 i<j\}$ [duplicate]
So I have a question:
Give a CFG for $\{a^i b^j : 2 i<j\}$
And this is my approach:
$S\to AB$
$A\to aAb\mid \varepsilon$
$B\to b \mid bB$
A confirmation, or correction, along with how you ...
4
votes
2answers
89 views
Two-State Turing Machine for Parenthesis Matching
In college we have been learning about theory of computation in general and Turing machines more specifically. One of the great theoretical results is that at the cost of a potentially large alphabet ...
3
votes
2answers
41 views
Give CFG and PDA for the words that start and end with the same symbol
I need to give a PDA and CFG for a language that contains all binary strings that start and end with the same symbol. I've created the CFG with no problem, but I'm stuck with the PDA and don't quite ...
1
vote
1answer
49 views
How can I show a linear languages are closed against concatenating with regular ones?
This was given as a homework problem but I have already submitted the assignment. I'd like to resolve it at this point for my own satisfaction.
Given that $L_1$ is a linear language and $L_2$ is a ...
3
votes
2answers
77 views
A pumping lemma for deterministic context-free languages?
The pumping lemma for regular languages can be used to prove that certain languages are not regular, and the pumping lemma for context-free languages (along with Ogden's lemma) can be used to prove ...
2
votes
2answers
71 views
Context free grammar construction
My problem with CFG is, I am to generally create ones that don't have requirements such as:
$\qquad \{a^m b^n \mid m \le n \le 2m \}$
I have no clue where to begin, and how to approach it. I was ...
1
vote
0answers
36 views
CFG to CNF conversion steps
I could find that different texts follow different steps in the conversion of CFG to Chomsky Normal Form. I couldn't find any presumptions they made in the conversion steps. I have some questions ...
2
votes
2answers
114 views
Pumping lemma for CFG doubt
I was looking at the pumping lemma for CFG. I came across the first problem $a^nb^nc^n$ and understood the answer. Then I thought of the problem $a^nb^n$. I know that this is context free and thought ...
1
vote
2answers
40 views
How to write Context Free Grammar with numerical restrictions
I am supposed to write a Context free grammar that generates the language:
$\qquad L(G) = \{0^{3n}1^{2n}0^{m}1^{m} : n \ge 1, m \ge 1\}$
I have the rules:
$$S \rightarrow 000S$$
$$S \rightarrow ...
-2
votes
2answers
42 views
A problem on first and follow sets of a grammar
Let me know the first and follow sets of the following grammar, also the explanation to it
$A \to Ba \mid Aa \mid c$
$B \to Bb \mid Ab \mid d$
Non-terminals: $\{A,B\}$
Terminals: $\{a,b,c,d\}$
-2
votes
0answers
33 views
A problem in Recursive descent parsing
Can somebody explain how the following string "aaa" can be parsed with the following grammar
$$
S\to aSa \mid \epsilon
$$
using recursive descent parsing?
-1
votes
1answer
28 views
Show that if L ⊆ {a}∗ is a CFL, then L is regular. [closed]
How can I Show that if L ⊆ {a}* is a CFL, then L is regular?
