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

learn more… | top users | synonyms

1
vote
1answer
14 views

state complexity for an nfa given a language

I've been having trouble proving the next statement: Let $L_n=\{ww, |w|=n\}$ prove that $L^c_n$ can be accepted by an NFA with at most $O(n^2)$ states. What i've been trying to do it's that the ...
-2
votes
1answer
32 views

Prove that $(L^*M^*)^* = (L\cup M)^*$

I would like to find out how to prove this statement. Thank you. Well I think that I proved one part of the statement, but my proof doesn't really look elegant. My proof of $(L\cup M)^* \subset ...
1
vote
1answer
50 views

Don't understand closure under string reversal

I am trying to learn from http://www.cs.uiuc.edu/class/su08/cs273/lectures/lect_06.pdf #2 and I understand everything except for the 2nd line of delta prime prime function, I having breaking down ...
1
vote
0answers
47 views

Given a non-deterministic Mealy machine $M$, if $L$ is regular, is $M(L)$ regular?

Consider a nondeterministic Mealy machine, $M$, defined as follows: $M = (Q, \Sigma, \Delta, \delta, \tau, q_0)$ where $Q$ is a finite set of states $\Sigma$ is an input alphabet $\Delta$ is an ...
0
votes
1answer
62 views

For two regular languages, why is the set of words from one that don't have a subsequence in the other also regular?

In general, a string $x$ is a subsequence of $w = w_1\dots w_n$ if there are integers $i_1<\dots< i_k$ such that $x = w_{i_1}\dots w_{i_k}$. The subsequence is proper if $k < n$ and $k > ...
3
votes
3answers
123 views

Clearing a Confusion regarding the Proof of equal no of a's and b's not being a regular language

I was wondering about its proof. The direct use of pumping lemma here is not a viability. So a certain teacher of mine proved this with the notion that $a^{n}b^{n}$ being a subset of this language ...
0
votes
1answer
43 views

Show that the regular languages are closed against taking “the second half” [duplicate]

Given $L$ is regular, the proof that $\mathrm{HALF}(L)$ is regular is pretty straightforward to me (e.g., #11 in this link): simply making a NFA and meeting in the middle with 2 original DFAs, the ...
1
vote
2answers
72 views

Proving Regularity of Languages that are 1/k of an already known regular language

There is this question in Kozen, that states if a language is regular then the first half would also be regular. Also I found a material on the internet that extends the thinking saying a language ...
-2
votes
0answers
16 views

Prefix closure of the language [duplicate]

If Σ is a finite set of symbols and α is a word in Σ ∗ , then a word β in Σ ∗ is said to be a prefix of α if α = β γ for some γ ∈ Σ ∗ . For example, the prefixes of the word abbab are λ , a , ab , abb ...
3
votes
1answer
72 views

Find a regular language that becomes non-regular if you cut away the middle third of all words

Let $A$ be a regular language, let $A'=\{xz\}$ such that for some $y,|x|=|y|=|z|$ and $xyz\in A$. Show that $A'$ is not necessarily regular language. This is an excercise of Sipser, I've no idea how ...
0
votes
2answers
49 views

Show that the language of words with even sum of positions of a letter is regular

Let $\Sigma=\{a,b\}$, and let $S(a)$ be sum of the positions of $a$ of string $S$. I want to prove $$L=\{S\in \Sigma^{*} \mid S(a)=0(\bmod 2)\}$$ is regular. What I was thinking is to do somehow keep ...
1
vote
0answers
37 views

What is regular about regular languages? [duplicate]

I am new to automata theory. I am well aware of the definition of regular language in automata, that is "a language is called a regular language if some finite automaton recognizes/accepts it" [MS]. ...
0
votes
1answer
53 views

Can the definition of regular languages be simplified?

Wikipedia says The collection of regular languages over an alphabet Σ is defined recursively as follows: The empty language Ø is a regular language. For each a ∈ Σ (a belongs to Σ), ...
2
votes
2answers
66 views

Language to Construct Finite State Transducer

I am attempting to write a Finite State Transducer module in OCaml, because I think it's a good exercise, which is because I have been teaching myself Natural Language Processing. You typically ...
-2
votes
1answer
51 views

How to write this regular expression

Consider the language over the alphabet $\sum= \{a\}$ containing strings whose length is either a multiple of 2 or 3 (including the empty strings). Writing a regular expression for this language
2
votes
1answer
30 views

Describing explicitly the MyHill-Nerode classes created by a language

I want to practice proving a language is regular or not using the MyHill-Nerode theorm, but for that I need to be able to describe the classes. Here's my practice attempt: For the language ...
-1
votes
3answers
241 views

Problem understanding DFA & NFA equivalence in Theory of Computation

Before asking this question,I had gone through Equivalence of NFA and DFA - proof by construction but my question is a bit different from that. I was reading Michael Sipser's ...
5
votes
1answer
70 views

Infinite non-regular decompositions of regular languages

The title pretty much says it: I'm interested in examples of infinite families of non-regular, pairwise disjoint languages whose union is regular. When is this the case? Or, from a different ...
0
votes
1answer
39 views

Is there a PDA for every Type 3 Grammar?

we learned that for every type 2 grammar G exists a PDA A with L(A) = L(G). But does for every type 3 grammar G exist a PDA A_G with L(A_G) = L(G)? I think it does, because type 2 grammar is a subset ...
3
votes
1answer
125 views

Generators of families of langauges?

From Wikipedia's definition of regular langauges The collection of regular languages over an alphabet $Σ$ is defined recursively as follows: The empty language $Ø$ is a regular language. ...
1
vote
1answer
188 views

Why is this language over {a,b,c} regular?

The language of all words over the alphabet {a,b,c} such that the number of as in the word minus the number of cs in the word is divisible by three. How is this language regular? Lecturer ...
1
vote
1answer
94 views

requirement for pumping lemma in regular language

I am a bit confused on the theory of the pumping lemma. As I know is used to decide if a language is regular or not. This is what I have understood so far though For a regular language $L$, there ...
-1
votes
2answers
148 views

Using the Pumping Lemma to show that the language $a^n b a^n$ is not regular

I've seen a lot couple of questions regarding the pumping lemma that are pretty similar to each other and this one is unfortunately not the exception. Most likely will be this question marked as a ...
1
vote
1answer
135 views

Draw a graph of DFA for a regular language

I'm trying to draw a DFA graph for the regular language where every chain: ...
2
votes
1answer
21 views

Concatenation property of regular languages

If L is the empty set and therefore a regular language, I know that L concatenated with sigma star is equal L; Are there any other languages that, when concatenated with sigma star will result in the ...
0
votes
3answers
117 views

Build a regular grammar for a regular language [duplicate]

The language considered is the infinite set of all chains that meet the following conditions. Conditions: ...
0
votes
1answer
72 views

Build a regular expression to define a regular language [duplicate]

The language is an infinite set of chains that are defined by the next conditions. Conditions: ...
2
votes
3answers
79 views

What is the regular expression to the given language?

I can't really find out, how can the following given Language be written down with regular expressions $ L = \{ a^{3k-1} b^n a^{2t} \mid n > 0; k, t\ge1 \} $ I had some guesses, but I don't know ...
11
votes
1answer
161 views

The number of different regular languages

My question is: Given an alphabet $\Sigma = \{ a,b \}$, how many different regular languages are there that can be accepted by an $n$-state nondeterministic finite automaton? As an example, let us ...
1
vote
2answers
123 views

Is $a^n b^m$ never regular if n and m have some relation between them?

I know what regular and context free language are and how regular language needs finite memory and other stuff. What concerns me is that I think if $a^nb^m$ such that $n$ and $m$ have some relation ...
-1
votes
1answer
94 views

induction proof for kleene star

i posted this on mathematics stack exchange here before i realised this one existed. i am going through some past exam paper questions on regular languages for some revision, and i am having a bit of ...
4
votes
1answer
79 views

What does $\{$ a set $\}^{+}$ mean in the context of languages?

I came across this notation and I don't know the meaning of it, or if it's a typo: $\{$ some set $\}^{+}$ What does the + mean, i.e., the plus operator applied to a set?
7
votes
1answer
119 views

Proving a language (ir)regular (standard methods have failed)

I'm currently trying to prove a language regular (for personal amusement). The language is: The language containing all numbers in ternary that have even bit-parity when encoded in binary. Now, I've ...
5
votes
3answers
460 views

Is it compulsory that every infinite set be non regular?

I am confused regarding the statements provided by one of our faculty regarding "Is it compulsory that every infinite set is non regular though every finite set is a regular set". Providing ...
3
votes
1answer
66 views

Regular expressions and semi-linear sets

In proving Parikh's Theorem, my Theory of Computer Science textbook defines a linear set as: $u_0 + \langle u_1, \dots, u_m \rangle = \{u_0 + a_1u_1 + \dots + a_mu_m \mid a_1, \dots, a_m \in ...
2
votes
1answer
111 views

Why is TIME(n log (log n)) \ TIME(n) = ∅?

In my computation book by Sipser, he says that since every language that can be decided in time $o(n \log n)$ is regular, then that can be used to show $TIME(n \log (\log n))\setminus TIME(n)$ must be ...
0
votes
1answer
45 views

a regular language so that $unary(L) \notin $Context Free Languages [closed]

I need a regular language $ L\subseteq \{0,1\}^{*} $ so that $unary(L)$ is not context free. unary of $L$ is defined by: $$unary(L) = \{0^{1x} : x \in L \}$$ Example $L = \{0, 11\} $ $\rightarrow ...
1
vote
2answers
40 views

NDFA associated with language L

Let A = $(Q, \Sigma, \delta, S, F)$ be a deterministic finite automaton associated with the language $L \subseteq \Sigma^*$ $L' = \{y \in \Sigma^*:\exists x\in L. |x| = |y|\}$ $L \subseteq ...
-2
votes
1answer
78 views

Is the language $\{ a^pb^q \mid p, q \text{ are prime} \}$ regular? [closed]

I am interested to know whether that language $$ L = \{ a^pb^q \mid p, q \text{ are prime} \} $$ is regular. How do you prove that it is not regular?
2
votes
1answer
57 views

Proving that the continuation of a non-regular language is not ω-regular

I want to prove that a language is not $\omega$-regular. The language I'm working with can be defined as: $$L = \{ a_1 \dots a_n x^\omega ~ | ~ n > 0, a_1 \dots a_n \in L^\prime \}$$ where ...
3
votes
1answer
85 views

Show that the pumping lemmas for context-free and regular languages are equivalent for unary languages

I want to show that for any language $L \subseteq \{ a \}^* $, $L$ satisfies the pumping lemma for context free languages if and only if it satisfies the pumping lemma for regular languages. I know ...
2
votes
0answers
66 views

If $L_1$ is regular and $L_1 \cap L_2$ context-free, is $L_2$ always context-free? [closed]

If $L_1$ is a regular language and $L_1 \cap L_2$ is a context-free language, does it mean that $L_2$ is a context-free language too? I attempted to prove that $L_2$ was not required to be ...
0
votes
2answers
104 views

Generating all strings that a regular expressions describe

I'm having trouble generating the set of strings, which a regular expressions describe. A typical regular expression can look like this: ...
2
votes
1answer
50 views

Is $L = \{ x \in \{ 0, 1 \}^* : |x| = 2^n $ for some natural number n $\}$ context free?

I was wondering if this language is context-free: $L = \{ x \in \{ 0, 1 \}^* : |x| = 2^n $ for some natural number n $\}$ I know that this language is not regular because it fails the pumping lemma ...
0
votes
1answer
51 views

If neither $L_1$ nor $L_2$ are context free then is $L_1 \cup L_2$ also not a context free language? [closed]

If two regular languages $L_1$ and $L_2$ are both not context free languages then is $L_1 \cup L_2$ also not a context free? I am aware that if $L_1$ and $L_2$ are context free languages then the ...
1
vote
1answer
40 views

Proving a language is not a regular language but a context free language [duplicate]

I have the languages $L_1$ and $L_2$ such that $L_1 = \{a^nba^n :n \in N\}$ and $L_2 =\{a,b\}^*\setminus L_1$. I want to prove that $L_2$ is not a regular language. I know that to prove that $L_2$ is ...
0
votes
1answer
58 views

Using the pumping lemma for a proof by contradiction [duplicate]

I'm trying to prove that the set of even-length strings with the two middle symbols being equal cannot be accepted by finite automata. I can explain why it cannot be accepted intuitively, but I'm ...
0
votes
1answer
77 views

Pumping lemma on {a^n | n=3^k} — help finishing the proof [duplicate]

I am working on a pumping lemma question and trying to prove that the following is not regular, but I can't finish the proof, if someone can help me it will be great. So I am given this language: $L ...
-2
votes
4answers
65 views

Concatenation of regular languages [closed]

Suppose we have two language L = {0^n|n>=0} M = {1^n|n>=0} We know both of these are regular languages. Will L.M (concatenation) be a regular language? ...
3
votes
1answer
168 views

Regular expression to show that all strings contain each symbol atleast once

I'm studying for my exam and I came across the following exam question from last year, the only way I know how to solve this is build a regex that accounts for all six different series of letters so ...