The regular-language tag has no wiki summary.
-6
votes
0answers
59 views
Context free language [closed]
Hi everyone i wonder DCFL(Deterministic Context free language ) - Regular language should be context free or not ? Is there anyone who can help me about this ? thanks in advance
-2
votes
0answers
25 views
Is language of binary representations regular? [migrated]
Let $bin(n)$ denote binary representation of an integer $n$. Let $L=\left\{bin(n^2):n\in\mathbb{N}\right\}$. Is $L$ a regular language?
I think one can prove that $L$ is not regular with pumping ...
-2
votes
0answers
44 views
Is given language regular? [migrated]
Let $L$ be a regular language. Is $\frac{1}{2}L := \left\{ w: \exists_u |u|=|w| \wedge wu\in L \right\}$ regular too?
I think the answer is YES. But I don't know how to prove it. I was trying to ...
3
votes
1answer
132 views
Context-free Grammar for a Context-free Language Intersecting a Regular Language (get the Maximum Number of Rules)
It is well known that the intersection of $L \cap R$ of a context-free Language $L$ and a regular Language $R$ is context-free. Each proof I have seen constructs a automaton (a PDA) that accepts $L$ ...
5
votes
0answers
133 views
The regularity of Markov chains with a threshold
(This question has been asked on math.se, with no response.)
I am studying Paz's "Introduction to Probabilistic Automata" and there is an exercise I cannot solve:
Ex. 11, p. 170: Let $\Sigma = ...
14
votes
1answer
259 views
Relation between $AC^0$ and regular languages
Let $\mathsf{REG}$ be the class of all regular languages.
It is known $\mathsf{AC}^0 \not\subset \mathsf{REG}$ and $\mathsf{REG} \not\subset \mathsf{AC}^0$. But is there any characterization for ...
0
votes
0answers
85 views
Fullness of regular expressions with exponentiation
Meyer & Stockmeyer proved many years ago that the following problem is NEXPSPACE complete, called "fullness of regular expressions":
Input: regular expression with exponentiation
Output: true if ...
0
votes
0answers
64 views
Automatic structures/functions: Is (Z,+) under a unary representation automatic?
The group $(\mathbb{Z}, +)$ is automatic (ala Khoussainov) when using the "standard" representation in a decimal base. But if I want to use a different representation of Z, encoding my integers with ...
9
votes
2answers
189 views
The significance of state complexity in automata and regular languages?
I'm reading "Concatenation of Regular Languages and Descriptional Complexity" by Galina Jiraskova, 2009 on the state complexity resulting from concatenation of two regular languages ( by Galina ...
4
votes
1answer
105 views
Getting an automaton from set of words in and out of a language [duplicate]
Possible Duplicate:
Is finding the minimum regular expression an NP-complete problem?
Let's suppose that I have an unknown language $\mathcal L$, I know only two (particularly large) sets ...
7
votes
1answer
156 views
Regular expressions of families of regular expressions
I was reading about the Star Height Problem and noticed that Eggan's family of regular expressions follows a simple pattern which can be described by a regular expression. My question is: are there ...
6
votes
0answers
411 views
minimizing size of regular expression
Suppose we have a regular language specified by a regex, for example, (ab|ac)* and we wish to find an equivalent regex with the minimal number of symbols, (a(b|c))*. Is there any efficient way to do ...
13
votes
1answer
851 views
Sufficient conditions for the regularity of a context-free language
It would be nice to collect a list of conditions that imply that a context-free language L
is regular, i.e. conditions of the form:
"if a given CFG/PDA has property P, then its languages is regular"
...
10
votes
2answers
431 views
Büchi automata with acceptance strategy
The problem
Let $A=\langle \Sigma, Q, q_0,F,\Delta\rangle$ be a Büchi automaton, recognizing a language $L\subseteq\Sigma^\omega$.
We assume that $A$ has an acceptance strategy in the following sense ...
14
votes
3answers
563 views
Regular languages from category-theoretical point of view
I noticed that regular languages over the alphabet $\Sigma$ can be naturally thought of as a poset, and indeed a lattice. Moreover, concatenation together with the empty language $\epsilon$ defines a ...
-4
votes
1answer
565 views
Proof that DFA that accepts string has NFA that accepts reversal of string
I have seen descriptions for an algorithm that can take a regular deterministic finite automata and create a non-deterministic finite automata that is guaranteed to generate the reverse of string ...
19
votes
0answers
189 views
Eilenberg's rational hiererchy of nonrational automata & languages — where is it now?
In the preface to his very influential books Automata, Languages and Machines (Volumes A, B), Samuel Eilenberg tantalizingly promised Volumes C and D dealing with "a hierarchy (called the rational ...
15
votes
3answers
479 views
What is the minimal extension of FO that captures the class of regular languages?
Context: relations between logic and automata
Büchi's Theorem states that Monadic Second Order logic over strings (MSO) captures the class of regular languages. The proof actually shows that ...
2
votes
1answer
248 views
FSMs with finite memory
Consider an FSM and a finite set of variables. The FSM has the special property that each state contains a set of commands, with each command taking the form of "variable = expr(variable, ...)" e.g., ...
15
votes
1answer
563 views
Why are regular languages called “regular”?
Why are regular languages (and from that regular expressions) called "regular"? There is lot of regularity also in context-free languages other types of languages.
I suppose that, in the beginning, ...
3
votes
2answers
256 views
Matching regular expressions using regular expressions
Is it possible to create a regular expression that matches regular expressions in any given notation?
Or, in other words, does there exist a unambiguous and full notation for regular expressions that ...
4
votes
1answer
236 views
On the relation for the Myhill-Nerode theorem/syntactic monoid of a language
In order to characterize regular languages one finds the following definition useful:
Let $\Sigma$ be an alphabet and $L\subseteq\Sigma^*$. Say that $x,y\in\Sigma^*$ are $\equiv_L$-related, and ...
10
votes
2answers
606 views
Counting words accepted by a regular grammar
Given a regular language (NFA, DFA, grammar, or regex), how can the number of accepting words in a given language be counted? Both "with exactly n letters" and "with at most n letters" are of ...
5
votes
3answers
308 views
Complexity lower bound for regular languages
Suppose I have a regular language $L$, and I would like to lower-bound the complexity of deciding membership in $L$. Suppose I know that the minimal DFA for $L$ has $N$ states.
I would like to claim ...
6
votes
0answers
300 views
Number of equivalence classes in regular languages as a function of DFA size
This question is related to a recent
question
by Janoma.
Background
In constraint programming, a regular global constraint $c$ over a
domain $D$ is a pair $(s, M)$ with $s$ a tuple of variables ...
10
votes
1answer
472 views
What is the number of languages accepted by a DFA of size $n$?
The question is simple and direct: For a fixed $n$, how many (different) languages are accepted by a DFA of size $n$ (i.e. $n$ states)? I will formally state this:
Define a DFA as ...
6
votes
2answers
253 views
Generating all instances of a regular language up to a certain length
Given a fixed regular language R, what is the complexity of generating all members of R with length at most $n$? Suppose some reasonable model (RAM with $n$-bit words?) and a write-only output tape. ...
4
votes
1answer
187 views
What is an unambiguous language in the sense of Schützenberger?
I'm reading Thomas Wilke's survey on the connections between Temporal Logic and finite automata, finite semigroups and first-order logic.
In Theorem 6 (by Kamp), the fragment ...
3
votes
6answers
984 views
What are regular expressions good for?
If you ask a question about parsing HTML with regex, you will certainly be referenced to this famous rant. Though there is not a canonical rant for it, I've also been told that regex aren't powerful ...
0
votes
0answers
154 views
is Language regular ? [closed]
Is this Language regular ?
L = {w ∈ Σ {Y, N}* : w contains at least two Y’s and at most two N’s}
My thinking way :
using pumping lemma I took w = uvw / uv = (Y)^n(N)^n (this case happen if only n = ...
0
votes
0answers
166 views
algorithm that can determine for every regular language L [closed]
can you please tell me how can I show that there exists an algorithm that can determine for every regular language L, whether or not |L| ≥ 5
16
votes
5answers
460 views
Ambiguity and Logic
In automata theory (finite automata, pushdown automata, ...) and in complexity, there is a notion of "ambiguity". An automaton is ambiguous if there is a word $w$ with at least two distinct accepting ...
0
votes
0answers
468 views
show that if L is regular, so is L-{lambda}? [closed]
please, help me I have exam after tomorrow and I couldn't figure it out.
thanks in advance!!!!
L = language
16
votes
5answers
1k views
A special class of languages: “circular” languages. Is it known?
Define the following class of "circular" languages over a finite alphabet Sigma. Actually, the name already exists to denote a different thing it seems, used in the field of DNA computing. AFAICT, ...
6
votes
2answers
994 views
Is JSON a Regular Language?
I was wondering if the JSON spec defined a regular language. It seems simple enough, but I'm not sure how to prove it myself.
The reason I ask, is because I was wondering if one could use regular ...
