Questions tagged [regular-languages]

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

Filter by
Sorted by
Tagged with
0
votes
1answer
26 views

Automata with minimal number of states using reverse

So, by the Bzozowski theorem, if A is DFA det(rev(det(rev(A))) would have minimal number of states. And for the most of them work. But for this example, I can't figure out why it doesn't. I have an ...
0
votes
1answer
20 views

Examples of Regular, Context-free and Context-sensitive languages

Assume the languages: $$ a) \, L_1 = \{ w \in \{b,c \}^* | \, w \, \text{contains 'bbc' as substring} \} $$ $$ b)\, L_2 = \{ 1^k 0^m 1^m | k,m \in \mathbb{N} \} $$ $$ c)\,L_3 = \{ w \in {0,1}^* | \,...
4
votes
1answer
307 views

Possessive Kleene star operator

Has anyone studied the consequences of the Kleene star in regular expressions to always be "possessive"? In other words, if * would always match as much as ...
0
votes
0answers
13 views

Given a DFA M, formally define an NFA N such that L(N) = {x in L(M) | x = reverse(x)}

The english description of the question is (from my understanding) N accepts all strings that are both palindromic (the same forwards as it is backwards) and accepted by M. After a lot of toil and ...
29
votes
2answers
1k views

Planar regular languages

In my class a student asked whether all finite automata could be drawn without crossing edges (it seems all my examples did). Of course the answer is negative, the obvious automaton for the language $\...
1
vote
1answer
35 views

Prove that a language is bounded if and only if it's finite

Let's assume $L$ is a language. $L$ is bounded if for some natural number $n \in \mathbb N$ applies $|x| ≤ n$, where $|x|$ is a length of a string, with every $x \in L$. Let's also assume that $L$ ...
0
votes
3answers
4k views

DFA for Strings with third symbol from RHS as 1

How can we make a DFA for given condition in title from alphabets {0,1} (binary). What can be the regular expression for this? My calculated expression is (a+b)*a(a+b)(a+b) , please correct me if i'...
17
votes
4answers
52k views

How to show that a “reversed” regular language is regular

I'm stuck on the following question: "Regular languages are precisely those accepted by finite automata. Given this fact, show that if the language $L$ is accepted by some finite automaton, then $L^{...
0
votes
1answer
36 views

Create automata from non regular grammar

I have two grammars: L → ε | aLcLc L → ε | aLcLc | LL This two grammars are equals but the first one is regular, so it produces a regular language and a ...
-1
votes
0answers
15 views

L' = { w | ww ∈ L where L is regular } [duplicate]

Let L be a regular language. We define another language L' = {w | ww ∈ L} . Show that L' is regular. I was trying to construct an automaton for L' but unable to construct it. Please help or please ...
12
votes
7answers
1k views

Is $A$ regular if $A^{2}$ is regular?

If $A^2$ is regular, does it follow that $A$ is regular? My attempt on a proof: Yes, for contradiction assume that $A$ is not regular. Then $A^2 = A \cdot A$. Since concatenation of two non-...
0
votes
0answers
22 views

Uncommon case in Arden's lemma $q_{2} = 1q_{2} \cup 0q_{2}$

I'm trying to get the regular expression of an automata but an state has a form that I don't know how to solve, the form on its simplest example is: $$q_{2} = 1q_{2} \cup 0q_{2}$$ What's the ...
8
votes
0answers
41 views

Regularity profiles

A standard exercise in formal language theory uses Lagrange's four-square theorem to construct a language $L$ such that $L$ isn't regular but $L^2$ is regular. (Let $A = \{ a^{n^2} : n \geq 0 \}$. ...
0
votes
0answers
31 views

If $L^2$ is regular. Does that imply L is regular [duplicate]

If $L^2$ is regular. Does that imply L is regular. I think L need not be regular. But I can't find any example where L is not regular but $L^2$ is regular. My teacher told me an example where L={$0^...
0
votes
0answers
46 views

How to prove this language is not regular?

I am currently learning Pumping Lemma and found this question. But I am not able to prove it not regular. L = { $0^n$ | n is power of 2}. So, here I considered w = $0^{2^n}$ where n is constant of ...
5
votes
1answer
467 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....
7
votes
2answers
928 views

Myhill-Nerode and closure properties

It is well known that regular languages are characterized by the Myhill-Nerode equivalence. For language $L$ over $\Sigma^*$ define the equivalence $x\sim_L y$ over $\Sigma^*$ iff for all $z\in\Sigma^*...
0
votes
0answers
24 views

Is there a language that pumps, but is not regular? [duplicate]

I'm looking for a concrete language that can be pumped but is not regular. I understand that closure properties can be used to further test if a language is regular/nonregular.
1
vote
2answers
95 views

How do i tell if a grammar is regular or not?

I know that a regular grammar has a definition $$\begin{align}S &\to aS\\ S &\to \lambda \end{align}$$ But I dont really know how to apply this information to check whether or not a grammar ...
1
vote
1answer
4k views

DFA Minimization: Finding all equivalence classes of $\mathsf{R_L}$ for language $011(0+1)^*011$

How do we find all equivalence classes of $\mathsf{R_L}$ for a language? Say I'm trying to look for all equivalent classes for the regular language $\mathsf{L}$ is $011(0+1)^*011$. Here's an ...
1
vote
1answer
64 views

Determining equivalence classes of $\{w \in \{0,1\}^*\mid$ the $k$-bit of $w$ from the right is 1$\}$

I want to formally write the equivalence classes of the following language: $$L_k = \{w \in \{0,1\}^*\mid\text{ the } k\text{-th bit of }w\text{ from the right is } 1\}$$ I understand the definition ...
0
votes
0answers
19 views

A deterministic finite state automata for finding all (potentially overlapping) regular expression matches?

I was working on a bioinformatics practice problem named Finding a Protein Motif on rosalind.info. In essence, I was given a particular regular expression ...
1
vote
1answer
66 views

Proving that L is not regular by showing that $\equiv_L$ has infinite index

Proving that L is not regular by showing that $\equiv_L$ has infinite index. $\Sigma$ = {a}, L = {$a^{3^n} : n \geq$ 0} My ideas: theorem of Myhill-Nerode: L $\in$REG $\Leftrightarrow$ $\equiv_L$ has ...
0
votes
1answer
24 views

Condition in Arden's rule

According to Arden's rule, the language equation $X= AX\cup B$, with unknown $X$, has the solution $X=A^*B$, provided $A$ does not contain the empty string. My question: what is the problem with the ...
2
votes
2answers
101 views

Proof: There exists an irregular language L such that LLLL is regular

As title. I consider finding a specific L to fulfill the condition stated to prove the statement, however, I have no luck in finding one. A senior gave me a hint that Lagrange's four square theorem ...
-2
votes
1answer
37 views

Regular Expression: Writing an expression with at least two characters in length? [closed]

A past exam question: (1) Consider the language, $L$, of strings over the alphabet $\{x, y\}$ of length at least 2 with the second symbol being $x$. For example, $yx$, $xxyy$, and $yxy$ are members ...
75
votes
10answers
103k views

How to prove that a language is not regular?

We learned about the class of regular languages $\mathrm{REG}$. It is characterised by any one concept among regular expressions, finite automata and left-linear grammars, so it is easy to show that a ...
1
vote
1answer
32 views

Pumping lemma regarding {a^2k w | w ∈ {a, b}*, |w| = k}

I had a question regarding the Pumping lemma for regular languages, I have been studying for an exam and came across the question {a^2k w | w ∈ {a, b}*, |w| = k}. In the website it lists the answer ...
-1
votes
1answer
15 views

Is finite subset of a set which contains all non regular languages a regular set?

Let A be a set which contains all non-regular languages. Then set B which is finite subset of A. Then will it be regular ? I know that A is not recursive enumerable set (undecidable). So I wonder ...
2
votes
1answer
40 views

How can the union of two 'context-free but not regular' languages be regular?

I cannot understand how the union of two languages which are context-free but not regular, can result in a regular language: If $L_1$ and $L_2$ are 'context-free but not regular' languages, defined ...
1
vote
1answer
50 views

Finding the equivalence classes of a language

I'm doing a problem where I need to find the $≡_A$ equivalence classes of the language $$A = \{ 0^{n}x \mid n \in \mathbb Z^+, x \in \{0, 1\}^*, \text{ and } \#_0(x) ≥ n \}. $$ The best way I've ...
1
vote
1answer
53 views

Can the difference of a non-regular and a regular language be regular?

I have some trouble understanding some exercises related to operations on regular languages.I tried to apply their closure properties, but I am not sure how to do the following exercises: If $L_2,L_3$...
4
votes
3answers
5k views

Irregularity of $\{a^ib^jc^k \mid \text{if } i=1 \text{ then } j=k \}$

I read on the site on how to use the pumping lemma but still I don't what is wrong with way I'm using it for proving that the following language is not a regular language: $L = \{a^ib^jc^k \mid \text{...
1
vote
5answers
9k views

Explaining why a grammar is not LL(1)

I need some help with explaining why a grammar is not LL(1). Let us take the following grammar: $$ \begin{align} S \rightarrow & aB \mid bA \mid \varepsilon \\ A \rightarrow & aS \mid bAA \\ ...
1
vote
1answer
47 views

Pumping Lemma on Language with subtracted length

My study group and I have had some back and forth on one exercise and I haven't found any matching solution online. The task looks as follows: Prove that $L$ is not regular given $$ L = \{ a^k b a^{m-...
1
vote
1answer
52 views

How to characterize equivalence classes induced by Myhill-Nerode theorem?

Given $L=\lbrace w\in \lbrace 0,1 \rbrace^\ast : N_0(w)=N_1(w) \rbrace$, where $N_0(\cdot)$ and $N_1(\cdot)$ mean the number of zeroes and ones respectively, I need to characterize the classes ...
7
votes
1answer
815 views

Time Complexity of Regular Languages

I wonder how I can go about proving that if a language L is decidable in o(nlog(n)) then L must be regular. I should probably mention that by "decidable" I mean "being decidable by single-tape ...
1
vote
1answer
164 views

Prefix/suffix property of language containing only empty word

Does language $L ={\varepsilon}$, where $\varepsilon$ - empty word has suffix/prefix property? The definition says that language has prefix/suffix property requires that there is no code word in the ...
1
vote
1answer
62 views

Meaning of L* if L is a language

I can't find anywhere the meaning of $L^*$, given that $L$ is a language. I know $^* $ means repetition, for example $0^*$ = $\{ \epsilon, 0, 00, 000, \dots \}$. Or if $A$ is an alphabet $A^*$ are all ...
6
votes
2answers
83 views

Can the regular image of a context-free language be undecidable?

I just need to know the truth or falsity of a simple statement. Let $L_1$ be a context-free language over an alphabet which contains some number of characters $\Sigma$, as well as a single, special ...
3
votes
2answers
98 views

Converse of pumping lemma for regular expressions

I want to come up with a language that satisfies the pumping lemma while not being a regular expression. I thought of $\{0^i1^j: i > j > 0\} $. The pumping seems to work just fine, and this is ...
1
vote
1answer
80 views

How can I find the Myhill-Nerode classes for the language A?

I have the following task (no homework). Find all equivalence classes of the Myhill-Nerode relation of the language $$ \mathrm{A} \triangleq\{w \in \Sigma^{*} | w\text{ does not end with }01\}\,. $$...
0
votes
0answers
18 views

regular expression with kleene closure [duplicate]

my question is if my regular expression R is 1* that means the language accepted is {^,1,11,111,1111...} in that case i don't understand the meaning what (R*)* means
0
votes
1answer
23 views

Counting number of states from a regular expression

Given the regular expression: $r=ab+((a+\epsilon)c^*)^*$. Let A be a non-deterministic automaton that accepts the language of r. How many states are in A? Answer the question without building A ...
2
votes
1answer
88 views

Finding a regular expression of a language

Our alphabet is {a,b} and we need to find a regular expression for the language of all words of the form $a^*b^*$, whose length is a multiple of 3. Obviously $(aaa)^*(bbb)^*$ is one of the options, ...
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 ...
0
votes
2answers
91 views

Does there exist a finite automaton for the given language?

The question is simple and given as, alphabet $A$ is $\{a, b\}$, and language $L$ over $A$: $L = \{w: w \in \{a, b\}^*, n(a) - n(b) = 1 \mod 3\}$. Here $n(a)$ = number of $a$ and $n(b)$ is number of $...
2
votes
1answer
90 views

How to choose a word to apply the Pumping Lemma?

I have some questions about the PUMPING LEMMA. First of all, I do not study computer science, I still go to school, but I'm very interested, so I could make mistakes. And sorry about my English :) ...
1
vote
1answer
24 views

A deterministic FA for $0^*1^*$ is required

A deterministic finite automaton without $\epsilon$ steps for the language $0^*1^*$ is required. Any nice picture ? I have created a NFA for this language which has 2 states $Q_1,Q_2$, both are ...
2
votes
1answer
44 views

Is $L(G) \subseteq L(R)$ decidable?

Is the following problem decidable? Given a context-free grammar $G$ and a regular expression $R$, is $L(G) \subseteq L(R)$? It is given that the following problem is undecidable Given a ...