Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [regular-languages]

Questions about properties of the class of regular languages and individual languages.

38
votes
0answers
1k views

Is there a regular tree language in which the average height of a tree of size $n$ is neither $\Theta(n)$ nor $\Theta(\sqrt{n})$?

We define a regular tree language as in the book TATA: It is the set of trees accepted by a non-deterministic finite tree automaton (Chapter 1) or, equivalently, the set of trees generated by a ...
13
votes
0answers
171 views

Using logic to prove non-regularity of a language

A language $L$ is regular if and only if it is definiable by a sentence in monadic second order logic (MSO) over strings (J.R. Buchi, Weak second-order arithmetic and Finite automata; Z. Math. Logik ...
12
votes
0answers
470 views

Test whether two languages are equal, when give in algebraic form

This sub-problem is motivated by Algorithm to test whether a language is regular. Suppose we have two languages $L_1,L_2$ that are expressed in "algebraic" form, as formalized below. I want to ...
5
votes
0answers
209 views

How to disambiguate symbolic regular expressions

What I mean by a "symbolic regular expression" (if there already is a different name for this I'm not aware of it) is a regular expression that may include exponents that are symbolic arithmetic ...
4
votes
0answers
337 views

DFA, lower bound on number of states, language with primes and remainders

This is an exercise from old exam on formal languages that I don't know how to solve: Let $p \ge 5$ be a prime number and $L_p$ be a language of words over $\{0,1\}$ that read in binary from right (i....
4
votes
0answers
335 views

How to prove “if every subset of a set is a CFL, then the set must be regular.”

"If every subset of a set is a CFL, then the set must be regular." I want to prove it, could anyone please give me some hints?
3
votes
0answers
39 views

Sets whose decimal expansions form a regular language

Write $\bar n$ for the decimal expansion of $n$ (with no leading 0). For a set $S$ of natural numbers, let its set of expansions (in base 10) be $\bar S = \{\bar n \...
2
votes
0answers
73 views

How to prove that a language created from a context-free gramar's left side is regular(or left-linear)?

Given a context-free grammar $G$, let $\longrightarrow_G$ be the (one-step) rightmost derivation relation, and $\longrightarrow^*_G$ its reflexive and transitive closure. Let $S$ be the start symbol ...
2
votes
0answers
93 views

concatenation of regular and DCFL

$S -> AB$ $A -> aA / epsilon$ $B ->aBb / epsilon$ What is the class of language generated by the above grammar ? I think that it generates $a^* a^n b^n | n>=0$ so it should be regular ...
2
votes
0answers
63 views

What kind of structural features of strings can be described by regular grammars?

Context-free grammars, as well as other types of grammars, can naturally associate structure with the strings of the defined language, for example tree structures in the case of context-free language. ...
2
votes
0answers
9k views

Is the class of non regular languages is closed under complementation?

This is the question I am asked and I am currently proving it using proof by contradiction something like this: Let's take some language L which is non regular. Let's assume compliment of L i.e. $(L^...
1
vote
0answers
60 views

What is the regular expression for the following language?

What is the regular expression for the following language? $$L = \{acbc: a,b,c \in \{0,1\}^+ \}$$ maybe we can say $$L = ((0 + 1)^+ 0 (0 + 1)^+ 0) + ((0 + 1)^+ 1 (0 + 1)^+ 1)$$ Is it true??
1
vote
0answers
16 views

Pseudo-random regex-searchable function

Let $L$ be the set of strings of length $n$ (say $n=400$, for example). Let $N = \{0,1,\dots,|L|-1\}$. I am looking for a function $f : N \to L$ with the following properties: $f$ is efficiently ...
1
vote
0answers
58 views

Set of infinite DFA's

$INFINITE_{DFA}\equiv \{(A)\mid A \text{ is a DFA and } L(A) \text{ is an infinite language}\}$ Here $ (A) $ denotes the encoding of DFA Is above language regular, CFL or recursive ? I know that ...
1
vote
0answers
45 views

Finding language family of given language

I came across following problem: Let $L_1$ and $L_2$ are two languages and both of them are accepted by DPDA. If $L=L_1-L_2$ is any language, then what is the smallest language family $L'$ belongs ...
1
vote
0answers
67 views

Is universality problem of single state NPDA decidable?

I came across following problem: Given single state non deterministic pushdown automata $M$, whether $L(M)=\Sigma^*$ is decidable? Now I know for DPDA/DCFG/DCFL, universality problem is ...
1
vote
0answers
61 views

NFA: If alphabet {0,1} is given, are you allowed to build a NFA with only 0?

Let's say there is the alphabet {0,1} given and you are supposed to build a NFA for language ...
1
vote
0answers
42 views

Are JS regexes really not able to parse HTML?

Many people have seen this fantastic meme answer before about how we should use a parser to parse HTML instead of using Regex. The argument is that HTML is not regular and thus cannot be parsed ...
1
vote
0answers
107 views

Regexp substitution and finite-state transducers

Many programming languages support a "regular expression substitution" operation: if r is a regular expression and s, ...
1
vote
0answers
134 views

Given a DFA $A$ and a CFG $G$, decide whether $L(G) ⊆ L(A)$

Propose a reasonably efficient algorithm to decide, given a DFA $A$ and a CFG $G$, whether $L(G) ⊆ L(A)$. I think that I have to prove it by computing the intersection of both (DFA,CFG), and then ...
1
vote
0answers
262 views

How to prove the regularity of one language given that another is regular?

Consider the following unary operation on languages: min(L) = {x ∈ L | no proper prefix of x is in L} Prove that regular languages are closed under this operation; that is, prove that if language L ...
1
vote
0answers
127 views

Is the language of all DFAs that accept the empty language regular?

Is $E_{DFA}$ in the class of regular languages? $\qquad E_{DFA} = \{ \langle D \rangle \mid D \text{ is a DFA }, L(D) = \emptyset\}$ My argument is that it is because all of the DFAs in $E_{DFA}$ ...
1
vote
0answers
93 views

Language of rationals is regular, what is the number set equivalent to PDA?

Consider rational numbers given as their decimal expansions, then for every number we can build a finite automaton able to accept it. To simplify the argument, assume that finite rational expansions ...
1
vote
0answers
78 views

Can regular expression captures be matched by a CFG being simulated by an $LR(k)$ parser?

I have seen this question: Are regular expressions $LR(k)$? and my question is slightly related. Suppose I have a regular expression: RE=(aa)?(aa) and I convert it to a grammar: G ::= A B A ::= C | (...
0
votes
0answers
38 views

Prove or Disprove: If A is regular and A ∪ B is not regular, then B is not regular

I'm doing a problem where I need to prove the following statement: If A is regular and A ∪ B is not regular, then B is not regular. In another similar problem that I did, I know that if A is regular ...
0
votes
0answers
19 views

What is “Phrase structure grammar”?

I'm undertaking Theory of Computation Classes. I came across this sentence while studying Recursively Enumerable Grammar: Type-0 grammars generate recursively enumerable languages. The ...
0
votes
0answers
61 views

Conversion from automaton to left linear grammar

I stumble across this problem: Give right linear grammar. The solution given was simple: $S\rightarrow bA$ $S\rightarrow aS$ $A\rightarrow \lambda$ $B\rightarrow bA$ $A\rightarrow aB$ Earlier ...
0
votes
0answers
76 views

Show that language is context-free

Let $A$ be a pushdown automata with input alphabet $\Sigma$ and stack alphabet $\Gamma$ and let $R \subseteq \Gamma^∗$ be a regular language. Let $L_R(A) \subseteq \Sigma^∗$ be a language of such ...
0
votes
0answers
31 views

Show that the set $\{uv | u \in L \ and\ v \notin L\}$ is regular

The full question is: Let $L$ be a regular language over $\{a, b, c\}$. Show that the set $\{uv\ |\ u \in L \ and\ v \notin L\}$ is regular I have the following answer, but I'm not sure if it's ...
0
votes
0answers
112 views

When proof by induction on length string is not possible?

I found out an exercise where you have to prove the correctness of the following CFG: Let $L=\{ 0^i 1^j|2i \leq j \leq 3i \}\:$ and $\: G: S\rightarrow 0S11 | 0S111| \epsilon$ claim: Every string $w ...
0
votes
0answers
20 views

Is there any algorithmic way to decide the equivalence classes in the nerode relation?

Consider the language $L= \{ x\in \{0,1\}^* |x$ ends with $00 \}$ The Nerode relation $R_L$ says $xR_Ly \iff \forall z\in \Sigma^*:xz\in L\iff yz\in L$ By looking at the language : I can conclude ...
0
votes
0answers
69 views

Are there any context-free languages that are not regular but can be generated using a right-linear or left-linear grammar?

I understand that every regular language can be generated using either a right-linear or left-linear grammar, however, does that go the other direction? In other words, do there exist any context-free ...
0
votes
0answers
84 views

Operations on regular languages

I am taking a course on natural language processing that assumes the students have some background on theory of computation. I dont, but have read up till chapter 3 of the book "Speech and Language ...
0
votes
0answers
163 views

Closure under swap operator

I am stuck on this problem and unsure how to proceed. I understand how to show that two languages are closed under regular operators, but not one like the 'swap' operator. Let swap : {a, b}∗ → {a, b}∗...
0
votes
0answers
83 views

Tool for NFA/DFA manipulation

I am look for a tool with any or all of the following features: Regular Expresstion to NFA converter that represents transitions as Binary Decision Diagrams NFA to DFA converter NFA minimization NFA ...
0
votes
0answers
116 views

Computing substring language on automata

Given a DFA, it is possible to compute the automaton that recognizes the language of its substrings (you can compute it as the automaton that recognizes the suffixes of its prefixes). I would like to ...
0
votes
0answers
56 views

Show that this language is not regular by Pumping Lemma

Over the alphabet $\Sigma=\{a,b\}$, we define $$L=\{a^pb^m: p\text{ is prime }, m>0\}+\{a^r:r\geq 0\}.$$ I must show that this laguage is not regular using the pumping lemma. I guess I should ...
0
votes
0answers
56 views

Empty words in regular languages

Let $L_1,L_2$ be any $\Sigma$-Languages, with $l_1\in L_1, l_2\in L_2$ If I have a regular Language $L(l_1(l_2l_1)^*l_2)$ would the word $\omega=l_2$ be recognized? I'm confused because if $\epsilon \...
0
votes
0answers
33 views

Find any kind of grammar for the language

Find any kind of grammar for the language L = {w ∈ Σ* | in w there are twice as many a's than b's} and reason its correctness. Where ...
0
votes
0answers
69 views

Regular language with number of a's same as number of b's

L = { x^n y^n / x,y belongs to (a+b)^* , number of a's in x = number of b's in y and n > 0} According to me it's regular because for any string $w$ belongs to $(a+b)^*$, we can divide the string into ...
0
votes
0answers
85 views

Does this grammar generate regular language?

$S \rightarrow AB$ $A \rightarrow aA \mid bA \mid \epsilon$ $B \rightarrow aBb \mid \epsilon$ Does this grammar generate regular language? According to me this grammar generates language of the ...
0
votes
0answers
55 views

proving L = {$a^{100}yy^r : \forall y \in$ {a,b}*} is not regular

I need to prove that L = {$a^{100}yy^r : \forall y \in$ {a,b}*} is not regular. i have tried using pumping lemma but couldn't get far with it. Any help in where i should go with it?
0
votes
0answers
476 views

Proof of every regular language has a LL(1) grammar

I tried some examples and found that LL(1) grammar always exist. I tried searching for formal proof but didn't find any. Can someone give a formal proof for the above statement?
0
votes
0answers
24 views

Operation on languages results in CFL

For every two languages $L_{1}$ and $L_{2}$ over the alphabet $\{ a,b,c,d \}$, we define the language $$L_{1} \operatorname{op} L_{2} = \{ \alpha\beta \mid \text{$\alpha \in L_{1}$ and $\beta \in L_{...
0
votes
0answers
81 views

What is the correct regular expression for this language?

Consider the following problem: $L$ is the language of regular expression $00^*11^*$. $DM(L)$ is the language obtained from $L$ by throwing away every even-length string belonging to it and for each ...
0
votes
0answers
195 views

Inverse Homomorphism expression

Consider the following expression :- $$h(h^{−1}(L))$$ I need an example where this expression can be superset of subset of L,but i am not able to get one.I am getting this equal to L always.How can ...
0
votes
0answers
78 views

How to prove for string of triplets that it is a Regular Language?

Let Σ2 = {0, 1}, and define Σ = Σ23. Informally, Σ* is the set of triples of the form (a, b, c) where a, b, c are single binary digits. Consider a string s ∈ Σ* : it is a sequence of such triples. ...
0
votes
0answers
72 views

Is there some problem in “promise-DSPACE(o(log log n))” that is also in “promise-DFA”?

Disclaimer I have no idea about complexity theory. If this question makes no sense or is wrong, mods are free to delete the question I´ve read somewhere that the problems that can be correctly ...
0
votes
0answers
31 views

Valid parenthesis Matching in MSO

What is the Monodic Second Order formula that encodes all binary strings that represent a valid parenthesis matching ? By this I mean 1s represent '(' and 0s represent ')' and at every position, ...
0
votes
0answers
46 views

Prove or refute that language $L=\{a^{n}b^{m}c^{{m}\choose{n}}\}$ is regular

I'm little confused with proving if this language is regular: $L=\{a^{n}b^{m}c^{{m}\choose{n}}\}$. What are $n,m$? Are they arbitrary? If yes, this language has only one word and I need to prove or ...