Questions related to formal languages, grammars, and automata theory
1
vote
1answer
21 views
Is it possible that the union of two recursively enumerable languages is decidable?
I'm trying to find two languages, $L_1, L_2 \in RE \backslash R$, such that $L_1 \cup L_2 \in R$.
I have already proved that if $L_1\cap L_2 \in R$, such $L_1, L_2$ don't exist (because otherwise ...
6
votes
1answer
48 views
Is the universe problem for one-counter automata with restricted alphabet size undecidable?
Consider the following universe problem.
The universe problem. Given a finite set $\Sigma$ for a class of languages, and an automaton accepting the language $L$, decide if $L=\Sigma^*$.
In [1], ...
1
vote
1answer
32 views
CNF: Recursion in CFG
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?
2
votes
4answers
61 views
Grammar that numbers of letters `c` is greater than number of letters `b`
Exactly as stated in the subject. I look for grammar which use letters $a, b ,c$ that numbers of letters $c$ is greater than number of letters $b$.
Example: $acbccba$ is generated by the grammar.
I ...
1
vote
1answer
47 views
If A many-one reduces to B, does the complement of A many-one reduce to the complement of B?
If A many-one reduces to B, does the complement of A many-one reduce to the complement of B? My gut says no but I am having a hard time finding a counterexample.
6
votes
0answers
78 views
Is the language of words containing equal number of 001 and 100 regular?
I was wondering when languages which contained the same number of instances of two substrings would be regular. I know that the language containing equal number of 1s and 0s is not regular, but is a ...
0
votes
2answers
41 views
Can this grammar be simplified?
So, I have a book here, which has an example for context sensitive grammar, and the grammar is the famous $0^n1^n2^n$ , and it has:
$$ \begin{align}
S &\rightarrow 0BS2 \mid 012 \\
B0 ...
0
votes
0answers
11 views
Program in R 3.0.0 [migrated]
I would like know how I can program the Gini Index and Lorenz Curve in the program Rx64 3.0.0.
I have loaded:
data(precip)
precip
gini <- function(precip,unbiased=TRUE, na.rm=FALSE){
...
3
votes
2answers
75 views
Please explain “decidability” and “verifiability”
I am trying to (intuitively) understand the two terms "decidability" and "verifiability".
I have done a reasonable amount of searching and going through the various texts I can put my hands on. ...
4
votes
3answers
102 views
Example of a non-context free language that nonetheless CAN be pumped?
So basically L satisfies the conditions of the pumping lemma for CFL's but is not a CFL (that is possible according to the definition of the lemma).
0
votes
2answers
53 views
How to convert NFA with null moves to NFA without null moves?
I am converting NFA with $\varepsilon$-moves to the NFA without $\varepsilon$-null moves. I understand that if, there is a $\varepsilon$-move between, $q_i$ and $q_j$, then all edges from $q_j$ have ...
0
votes
1answer
87 views
Proof that the regular languages are closed under string homomorphism
Where can I find a proof of this? Thanks!
2
votes
1answer
58 views
Is $L$ always context free?
Consider formal language $L$ over finite alphabet $\Sigma$ consisting of all words over $\Sigma$ that have non-trivial period (non empty prefix that is also a suffix). Is $L$ always context free?
...
-2
votes
1answer
56 views
PDA with 2 stacks
I am doing homework in Formal Languages. I urgently need a language which can be recognised by 2 PDA's but not with 1 PDA. Thanks
3
votes
1answer
46 views
What does it mean to say that a language is “effectively closed” under an operation?
I've been reading some formal language theory papers, and I've come across a term that I don't understand.
The paper will often refer to a set being "effectively closed under intersection" or other ...
2
votes
2answers
116 views
Can a language have $\Sigma^{*}$ as its syntactic monoid?
As per the title I was wondering if it's possible for a language $L \subseteq \Sigma^{*}$ to have $\Sigma^{*}$ as its syntactic monoid and if so could one give an example of such a language? I first ...
2
votes
0answers
25 views
Classes of NFAs which allow efficient subset testing or unambiguity conversions
I'm doing some research regarding NFAs and inclusion problems with them. I know that in general, the inclusion problems, and converting to an unambiguous NFA, are both PSPACE-complete.
I'm wondering, ...
7
votes
1answer
147 views
Is the language of binary representation of perfect squares regular?
Let $\mbox{bin}(n)$ denote the binary representation of an integer $n$. Let $L = \{ \mbox{bin}(n^2) \mid n \in \mathbb{N} \}$.
Is $L$ a regular language?
I think one can prove that $L$ is not ...
0
votes
1answer
28 views
Weak Precedence Grammar and 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 ...
2
votes
2answers
68 views
What type of formal notation is being used here to represent functional algorithms?
Interested in learning more about algorithm design in functional programming, I picked up Andrew Bird's Pearls of Functional Algorithm Design. I have experience with a number of programming ...
0
votes
2answers
102 views
How to take complement of a language?
I'm stuck on this question about context-free languages and was hoping for some clarification.
$\qquad L = \{a^i b^j c^k \mid i=j, i=k\}$
is not context-free. Show that its complement is ...
2
votes
2answers
113 views
Is {xyx | |x|≥1} context-free?
Is $L=\{ xyx \mid x,y \in \{a,b\}^* \text {and } |x| \ge 1 \}$ context-free?
If yes, please explain how we can write grammar or create a PDA for it. If not a CFL, then prove it through pumping ...
11
votes
0answers
210 views
Is this strange language context free?
Is the following language context free: $L = \{ uxvy \mid u,v,x,y \in \{ 0,1 \}^*\text \{ \epsilon \} \ ,\ \mid u \mid = \mid v \mid \ , \ u \not= v \ , \ \mid x \mid = \mid y \mid \ , \ x \not= y \ ...
2
votes
1answer
65 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)$ ...
2
votes
1answer
106 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
55 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 ...
16
votes
0answers
142 views
Asymptotics of the number of words in a regular language of given length
For a regular language $L$, let $c_n(L)$ be the number of words in $L$ of length $n$. Using Jordan canonical form (applied to the unannotated transition matrix of some DFA for $L$), one can show that ...
2
votes
0answers
30 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
54 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
83 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 ...
1
vote
1answer
45 views
Using pumping lemma to show $L = \{a^i b^j a^k \ | \ k > i + j\}$ cannot be accepted by an FA
$L = \{a^i b^j a^k \ | \ k > i + j\}$
Use the pumping lemma to show that this language cannot be accepted by an FA.
Proof:
Suppose $L$ can be accepted by an FA.
Suppose a string $s = ...
2
votes
1answer
63 views
How to show that L = L(G)?
Specifying formal languages by giving formal grammars is a frequent task: we need grammars not only to describe languages, but also to parse them, or even do proper science. In all cases, it is ...
0
votes
2answers
50 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
199 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 ...
3
votes
1answer
90 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 ...
6
votes
1answer
104 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
112 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$ ...
2
votes
1answer
23 views
Chomsky form for language of single alphabet member
I'm a bit confused as to how to represent the Chomsky form for the language L that generates all strings with the alphabet {a}
My approach was
...
0
votes
1answer
48 views
How to generate a pushdown automata for accepting a language?
I have an exercise in my book to come up with a pushdown automaton accepting a language.
The exercise is to come up with a state diagram for the PDA accepting the language of all odd-length strings ...
0
votes
1answer
67 views
Giving a regular grammar for the language
I am trying to brush up on my regular grammar knowledge to prepare for an interview, and I just am not able to solve this problem at all. This is NOT for homework, it is merely me trying to solve ...
6
votes
2answers
71 views
Regularity of the exact middle of words from a regular language
Let $L$ be a regular language.
Is the language $L_2 = \{y : \exists x,z\ \ s.t.|x|=|z|\ and\ xyz \in L \}$ regular?
I know it's very similar to the question here, but the catch is that it's not a ...
2
votes
1answer
32 views
How to interpret this formal language definition?
I am asked to construct a PDA to accept the language:
$\qquad \{w \in \{0, 1\}^* : \#_{0}(w) \ge \#_{1}(w)\}$
I am wondering how to interpret the $\#$ symbols and everything. Could someone please ...
3
votes
2answers
54 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
51 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 ...
0
votes
1answer
56 views
Regular expression for odd binary numbers without leading zeros
I have to write a regular expression that accepts any odd binary number not preceded by a 0. the best I can come up with is $1(0\cup1)^*1$, but that doesn't match just 1. The best it matches is 11.
2
votes
2answers
73 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 ...
4
votes
4answers
129 views
Proof that regular languages are closed against taking the even-length subset
This question is on the GRE Computer Science test booklet (not homework). I tried applying closure properties of regular languages but no success.
Suppose $L$ is a regular language over $\Sigma = ...
4
votes
2answers
148 views
Can a two-stack PDA accept language $a^nb^mc^nd^m$ which is not context-free?
Can a two-stack PDA accept language $L=\{a^nb^mc^nd^m \mid n \geq m\}$, which has no context-free grammar?
I don't believe this has a context-free grammar, but please correct me if I'm wrong.
3
votes
2answers
66 views
Does $c^*(b \cup (ac)^*)^*$ define all strings over $\{a,b,c\}$ that don't contain the substring $bc$
I'm reading my textbook and it claims that the regular expression $c^*(b \cup (ac)^*)^*$ defines the language $L$ over $\{a,b,c\}$ which consists of all strings that do not contain the substring $bc$. ...
5
votes
3answers
49 views
For regular languages A and B, determine whether B might match early in (A B)
I have two regular languages A and B, and I want to determine whether there is any pair of strings, a in A and b in B, such that (a b) is a prefix of a string in (A B) and the left-most ...
