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

learn more… | top users | synonyms

6
votes
0answers
49 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
413 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
36 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
97 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
0answers
20 views

A Java implementation of the Transitive closure method to generate a regular expression from a finite automata [closed]

I am working on a small application that collects some important operations about automatas. and there is my problem : I Can't find what's wrong with this implementation since 2 days ago : ----> ...
0
votes
1answer
42 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 ...
0
votes
2answers
33 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
67 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
52 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
53 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
56 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
64 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
47 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
47 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
0answers
56 views

Complexity of Languages [closed]

1) Find language $L_1 \subseteq L_2 \subseteq L_3$ such that both $L_1$ and $L_3$ are not context-free languages, but $L_2$ is a regular language. 2) Find language $L_1 \subseteq L_2 \subseteq L_3$ ...
1
vote
1answer
35 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
50 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
53 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 ...
-3
votes
4answers
54 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
107 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 ...
2
votes
0answers
53 views

Prove Single-Tape and Non-write Turing Machine can Only Recognize Regular Language?

Here is the problem: Prove the single-tape TM that cannot write on the portion of the tape containing the input string recognize only regular language. My idea is to prove that this particular TM ...
-1
votes
1answer
50 views

Given 2 regular languages and their DFA's, how to construct the DFA of the union?

Suppose $L1, L2$ are both regular languages and $A1, A2$ are their corresponding DFA's. How can I construct a new DFA for the regular language $L1 \cup L2$?
1
vote
0answers
40 views

Proving a language is regular or non-regular [duplicate]

I'm struggling a bit to understand two of the problems we were given in class. Could someone look over my work and maybe give me a few hints? State whether the following languages are regular or not ...
0
votes
2answers
80 views

A flawed theorem about regular languages

I am struggling with this question for a very long time and just can't find the flaw. So I am given a false Theorem: The language ${awwa \mid w \in {a,b}^* }% is regular. Well, that part is ...
2
votes
0answers
38 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. ...
10
votes
4answers
494 views

Regular language not accepted by DFA having at most three states

Describe a regular language that cannot be accepted by any DFA that has only three states. I'm not really sure where to start on this and was wondering if someone could give me some tips or ...
3
votes
1answer
160 views

Kleene star of an infinite unary language always yields a regular language

Let $L = \{a^n \mid n \ge 0\}$, where $a^0 = \epsilon$ and $a^n = a^{n-1}a$ for all $n \ge 1$. Thus $L$ consists of sequences of $a$ of all lengths, including a sequence of length $0$. Let $L_2$ be ...
-1
votes
2answers
92 views

Prove that languages which contain words whose lengths are multiples of a constant are regular

This is a problem involving the theory of regular languages. I am stuck on this problem and do not know how to solve this type of problem. Prove that the language $B_n = \{ a^k \mid k \text{ is ...
-1
votes
1answer
33 views

Left Linear Grammar: How to construct?

I need help constructing a Left Linear grammar for the language $L = \{ a^n b^m c^p \mid n\geq 2, m\geq 3, p\geq 4 \}$ Here is what I have so far, I know : $N = \{S\}$ $T = \{ a, b, c \}$ $P = ...
3
votes
2answers
72 views

Complexity of CFG grammar for a regular language

I know that each regular language can be generated by a CFG. This makes, in one sense at least: context-free languages more general than regular languages. Are there known results about the ...
5
votes
2answers
65 views

Context-free language and regular expressions

I have the following context-free language: S -> ASa | b A -> aA | a I don't understand why this is not regular. I first said that it's generated by the ...
1
vote
2answers
105 views

Do Kleene star and complement commute?

I am having hard time solving the following problem. Are there any languages for which $$ \overline{L^*} = (\overline{L})^* $$ Assuming $\emptyset^* = \emptyset$, if I consider $\Sigma = ...
1
vote
1answer
60 views

Are there regular languages between every two non-regular languages?

I have a question regarding regular languages. Given that $L_1$ and $L_2$ are non-regular languages, can a regular language $L$ exist so it is a subset of $L_2$ and $L_1$ subset of $L$? To be more ...
1
vote
1answer
40 views

How do I use the Myhill-Nerode theorem to show that a language is not regular?

My language is the repetition of 0 to a length that's a power of 2: $L = \{ 0^k \mid k=2^n, n \geq 1 \}$ I want to know how to use the Myhill-Nerode theorem to show that this language is not ...
0
votes
0answers
68 views

Proving a regular expression is correct [duplicate]

I'm working on homework for my formal languages and automata course. The text we are using is the first edition of Hopcroft and Ullman (1979). Specifically, I'm unsure how to justify that my regular ...
1
vote
1answer
113 views

Prove that the language L = {a^(m+n) b^m a^n | m, n ≥ 0} ∪ {a^m b^n a^(m+n) | m, n ≥ 0} is not regular [duplicate]

In general, how can we go about proving that union of two languages as non regular. In this case, the individual languages can be proved as non regular using pumping lemma. How can we apply pumping ...
2
votes
0answers
59 views

Why CFG can specify structure of sentence but Regular grammar cannot? [duplicate]

CFG can specify structure of sentences but Regular grammar can only specify strings sequentially. Is it because DFA has only one bit memory?
1
vote
1answer
66 views

Proving that {0^{2^k}} is not regular with the Myhill-Nerode theorem [duplicate]

My language is the repetition of 0 to a length that's a power of 2: $L = \{ 0^k \ni k=2^n, n \geq 1 \}$ I want to know how to prove that this language is not regular. I have attempted the proof ...
1
vote
3answers
72 views

How can both |y| = 0 and y⁰ = ε hold in the Pumping lemma?

There is something in the pumping lemma that I do not quite understand, namely if $s$ is at least of length $p$, then we could split it to $xyz$ such that the following conditions are met: For each ...
4
votes
2answers
796 views

Difference between 1* + 0* and (1 + 0)*

I know that (1 + 0)* is the set of all bit strings; but isn't 1* + 0* the same thing?
0
votes
2answers
78 views

Regular language concatenation with superset

Let $A$ be some alphabet. $A$ itself is a regular language. $E = A^*$ is regular language over $A$. $E$ is a superset of all languages over $A$, regular or otherwise, i.e $E$ contains every possible ...
2
votes
1answer
71 views

Is this the correct way to use the pumping lemma?

I've been watching lectures from Coderisland on YouTube about finite state machines, DFAs and NFAs, and in one discussion he talks about how to use the pumping lemma to show how a language is not ...
0
votes
0answers
15 views

Pumping lemma with two r languages [duplicate]

I have two questions about how to use pumping lemma for regular languages to show that two languages are not regular. I would appreciate if someone can confirm if my answers make sense, and if not, ...
1
vote
1answer
43 views

Decidability of an regular expression

I have this question about if the decidability of an regular expression and would appreciate if someone can check my answer and see if it makes sense, and if not, what is missing. Be A = {(R)|R it ...
1
vote
1answer
93 views

Proof that {$a^m b^n$ | m!=n} is not regular [duplicate]

I know that the language $\{a^m b^n | n\neq m\}$ satisfies the pumping lemma, but it's still not regular (I have to count the # of a's and b's). How can I formally prove it?
1
vote
1answer
33 views

Has there been a lexer that takes in much more than a regular language?

I understand the restrictions, because a regular language is expressive enough to allow all types of tokens. And even if some context is needed in many languages to tokenize properly, they all seem to ...
7
votes
2answers
151 views

Smallest DFA that accepts given strings and rejects other given strings

Given two sets $A,B$ of strings over alphabet $\Sigma$, can we compute the smallest deterministic finite-state automaton (DFA) $M$ such that $A \subseteq L(M)$ and $L(M) \subseteq \Sigma^*\setminus ...
5
votes
2answers
93 views

What is the field studying the search and generation of computer programs?

This Github repo hosts a very cool project where the creator is able to, give an integer sequence, predict the most likely next values by searching the smallest/simplest programs that output that ...
4
votes
1answer
151 views

Why is deciding regularity of a context-free language undecidable?

As I have studied, deciding regularity of context-free languages is undecidable. However, we can test for regularity using the Myhill–Nerode theorem which provides a necessary and sufficient ...
0
votes
1answer
48 views

Regular language using pumping lemma [closed]

a^2n b^(2n+1) is a regular language. I am not able to decompose it in xyz so that I can pump any power of y as per pumping lemma. Please help me out.