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

learn more… | top users | synonyms

0
votes
0answers
16 views

Proving that $\{0^nw1^n\mid n\geq 0, w\in\{0,1\}\}$ is irregular [duplicate]

How can I prove that the language $L = \{0^nw1^n\mid n\geq0,w\in\{0,1\}\}$ is irregular? I've tried the pumping lemma but that seems not to work.
-4
votes
0answers
23 views

Prove or disprove (r*)* ≡ r* [duplicate]

$(r$1* )* $≡ r$1* My intuition says that these two are equivalent in the strings they will accept/generate. I am not sure how to prove it if such is the case.
2
votes
1answer
27 views

Prove that language of possible stack content is regular

So, here's the problem: Suppose that $A=(Q,\Sigma,\Gamma,\delta,s,\bot, F)$ is a PDA, let $$L = \{ \gamma \in \Gamma^* \hspace{5pt}|\hspace{5pt} \exists_{x,y\in \Sigma^*} \exists_{q\in Q}: ...
-1
votes
0answers
16 views

Convert regular expression to FA?

I am trying to solve a practice problem from my textbook which is to draw an FA from this language: L(ab* a*) U L((ab)*ba) I need help to draw the second part L((ab)*ba). I know the shortest string ...
0
votes
1answer
31 views

The Chomsky–Schützenberger representation theorem

I've been trying to proof The Chomsky–Schützenberger, but I stuck on creating regular language from that theorem. I mean reagular language, which is intersected with Duck language. Could anyone give ...
1
vote
2answers
69 views

Write a regular expression - Contains an equal number of 01 and 10 subtrings

I have this language: And ive worked on a DFA where i can move on to create the RE. Here is my DFA: What im trying to do now is using ardens theorem to get the Regular expression however I'm ...
3
votes
1answer
21 views

Can an (extended) regular grammar have multiple nonterminals in its RHS?

Standard (right) regular grammars have three kinds of rules: A <- "" A <- "a" A <- "a" B This is OK for a theoretical point of view, but a big ...
0
votes
1answer
35 views

Context free Grammar and regular set

I read a question and I don't understand it, is the set consisting of: production rules of Grammars that are CFGs, itself a regular set? The only thing I know is that the type 3 is under the type 2 in ...
0
votes
1answer
25 views

Right linear grammar special case

According to the definition, the productions of a right linear grammar should have the form of $A\to xB$ or $A\to x$, does $A\to B$ or $A\to xy$ count as productions of a right linear grammar? $A\to ...
-3
votes
0answers
12 views
-4
votes
0answers
11 views
0
votes
0answers
43 views

Calculating Big-O

I was asked to find the O-complexity of the algorithm accepting the language {0^(2^k) | k>=0} meaning the length of a string in the language will be of a power of two. (using a turing machine) $ The ...
3
votes
1answer
33 views

Practical Applications of regular grammars

A regular grammar is a mathematical object, $G$, with four components, $G = (N, Σ, P, S)$, where. $N$ is a nonempty, finite set of nonterminal symbols, $Σ$ is a finite set of terminal symbols , or ...
1
vote
1answer
29 views

What name for an algorithm is more correct: Kleene's algorithm or McNaughton-Yamada algorithm?

The perhaps most widely known algorithm converting finite automata into rational expressions is usually known as Kleene's algorithm. However, Sakarovitch in his book Elements of Automata Theory ...
1
vote
1answer
23 views

How can I show context free grammars are strictly more expressive than regular expressions with an example?

I need to show a CFG can express everything that can be expressed by a regular expression, and something that cannot.. I have no idea what example is traditionally used for this.
1
vote
1answer
34 views

How to improve the accuracy of automatic conflict resolution?

A little background information from my previous question:http://english.stackexchange.com/questions/318528/conflict-resolution-how-to-decide-if-two-words-are-generally-unmistakable When a court ...
1
vote
1answer
56 views

Show that language generated by grammar is regular

We have grammar with nonterminals $ X_1,...X_n$ terminals $V_t$ and rewriting rules of form: $X_i \rightarrow a \in V_t $ $X_i \rightarrow X_jX_k, \ i \ge j , \ i > k $ How can I show that ...
7
votes
2answers
1k views

Will $L = \{a^* b^*\}$ be classified as a regular language?

Will $L = \{a^* b^*\}$ be classified as a regular language? I am confused because I know that $L = \{a^n b^n\}$ is not regular. What difference does the kleene star make?
1
vote
2answers
61 views

Can a regular language have uncountably many strings?

Obviously it can have a countably infinite number of strings. (Take the language descibed by the regular expression 0* as an example.) But can a RL have uncountably many strings? I'm leaning toward ...
0
votes
2answers
32 views

Is the given language finite or infinite?

I have an idea regarding whether this language is finite or not, but for some reason I am still having some issues regarding exactly grasping what makes a language finite or infinite. I know that ...
0
votes
2answers
69 views

If L is a regular language, how to prove that L' is also regular?

I've been trying to construct a proof of the following statement the whole day but I got stuck: If $L$ is a regular language, the language $L_{}{'}$ consisting of all words in $L$ containing the ...
0
votes
0answers
27 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}$ ...
6
votes
2answers
98 views

How similar are two DFAs? -not just binary equivalence-

Are there any measures to compute similarity (or distance) between two DFAs? If yes, which are the main references? I need a measure of similarity, not only a (binary) equivalence test. ...
1
vote
1answer
44 views

Languages having only one Myhill–Nerode equivalence class

Consider the alphabet $\{a,b\}$, for which languages does the Myhill–Nerode equivalence relation have exactly one class? From what I understand about equivalence classes, each state is ...
-1
votes
1answer
25 views

Give regular expression on language [duplicate]

What is a regular expression for $L_1=\{a^{2n} b^{3m+1} \mid n \geq 1, m \geq 0\}$?
0
votes
1answer
30 views

Is the union of a non-regular and a regular language regular?

I am studying Automata and stuck in a question that says: Is the following a regular set {a^p, where p is prime} U {even-length strings}? As we see here this language consists of two sub-languages. ...
0
votes
2answers
60 views

Prove that the language of squares is not regular using homomorphism

If a language like $L$ is regular, then any homomorphism of $L$ is regular too. So, if $h(L)$ is not regular, then we can conclude that $L$ is not regular. Assume that the language $L=\{yy:y \in ...
1
vote
1answer
40 views

What's the difference between the concatenation and union of symbols within a language

I feel like I'm confusing myself perhaps but I'm having a bit of trouble figuring out how exactly this language works. I'm given the following regular expression (a + b)* (abba* + (ab)*ba) Can ...
1
vote
1answer
74 views

Show language is not regular

Show that the following languages are not regular in two ways: first by using closure properties then by using the Pumping lemma: $$\text{(1) L1} = {a^n b^k c^{n+k} : n >= 0; k >= 0}$$ ...
2
votes
1answer
66 views

Show L1 /L2 is regular [duplicate]

Let $L_1$ and $L_2$ be two languages over an alphabet $\Sigma$. The quotient of $L_1$ and $L_2$ is the language $L_1/L_2 = \{x : \exists y \in L_2, xy \in L_1\}$ Show that if $L_1$ is ...
2
votes
1answer
95 views

Proving that the scramble of a regular language is context-free

For strings $w$ and $t$, if they have the same length and comprise the same characters (namely, they are two permutations of these characters), then $w\sim t$. For a string $w$, define an operator ...
2
votes
1answer
36 views

Difference between a minimal DFA and a canonical DFA

given a language L,a DFA M that recognize L is minimal if M is the DFA with the minimum number of states. In order for this to happen M does not have neither unreachable nor equivalent states. The ...
0
votes
1answer
49 views

If L is a regular language then the language replace(L,σ,τ) is also regular

I am stuck at the following problem: Prove that if $L$ is a regular language over some alphabet $\Sigma$ and that $\sigma, \tau \in \Sigma$, Then the language $replace(L,\sigma,\tau)$ is regular. ...
2
votes
1answer
25 views

Can a non-regular language be made regular via concatenation when they don't share characters?

So this is a follow-on question to my other question (Can we make a non-regular language regular via concatentation?). Given the following, $L = \{0^n1^m2^m \mid n>1, m>1\}$ $A = \{0^n \mid ...
4
votes
1answer
40 views

How do I show that an equivalence class of a language containing an empty string is infinite

The question is as follows: Let $L$ be a language (not necessarily regular) over an alphabet. Show that if the equivalence class containing the empty string $[ \epsilon ]$ is not $\{ \epsilon ...
7
votes
5answers
891 views

Can we make a non-regular language regular via concatentation?

My question is basically given three languages A, B and L, where L is A and B concatenated together and B is proven to be non regular, is it possible to find an A that makes L regular?
-1
votes
1answer
143 views

What is the difference between formal language, regular language and regular expression? [closed]

I want to know the difference between these three languages and it would be great if you would give some examples as well, thank you. :)
2
votes
2answers
37 views

Closure under reversal of regular languages: Proof using Automata

I have been studying the closure properties of regular languages, referencing the book Introduction to Automata Theory, Languages, and Computation by John E. Hopcroft and Jeffery D. Ullman. Under the ...
1
vote
1answer
27 views

A regular expression for an automaton which accepts strings with no more than 3 consecutive zeros [duplicate]

This is the automaton I want to find the regular expression for: As you see, states Q1 to Q4 are accepted and Q5 is a kind of trap. This automaton accepts strings that have no more than 3 ...
1
vote
1answer
48 views

Showing the the language represented by a set is regular

Is the language $L = \{ w \mid w $ is $ 3^n - 1 $ in some given representation $, n > 0 \}$ regular? I know that it is regular. If each element in $L$ is represented as decimal numbers, $L = \{ 2, ...
2
votes
1answer
49 views

How to pick w for the Pumping lemma if the language has no clear pattern?

I'm trying to understanding using the pumping lemma to prove that a language is not regular. I sort of understand how it works when the language describes strings with a particular form, like in this ...
-2
votes
1answer
56 views

Regular expression of a given language [closed]

Could somebody please confirm if a regular expression of language: $$ L := \{b(ab)^n a^m \mid n, m \geq 0\} $$ is $$\{b, (ab)^* a^*\}? $$ And if not, could somebody please tell me why?
-1
votes
1answer
74 views

Converting a language to a PDA?

I am trying to convert the follow language $$L = \{0^m1^n \ | \ 0 \le m \le n \le 2m\}$$ We have an exam in 2 days and the professor didn't teach us much about PDA's. They will be on the test though ...
2
votes
2answers
57 views

Proving a CFG is ambiguous?

I have a CFG: S --> 0S1S | 1S0S | ε I'm trying to prove that it is ambiguous, but the steps to proving so are confusing me. So if I pick a string, let's say ...
3
votes
1answer
90 views

Non-regularity of the set of primes in unary encoding using Myhill-Nerode

I have found many proofs for this using pumping lemma, I'm curious of how to proof it via Myhill-Nerode theorem. Suppose $L= \{a^p \mid p \text{ is prime}\}$ is regular. Then we have congruence such ...
0
votes
0answers
22 views

How do I prove a language is regular? [duplicate]

I've done a lot of research on this topic, but still don't feel very confident about it. Let's say the example is: For a language L over an Σ, define N(L)={w∈Σ∗: wk∈L for some k∈Σ∗}. Prove that, if L ...
1
vote
1answer
84 views

Regular and Non-Regular Language

My friends and I are taking a formal languages class and for one of our homework questions we have to prove if these languages are regular: 1) L = {apaqi : p and q are fixed integer values, i >= 0} ...
-1
votes
1answer
78 views

Confusion in Pumping Lemma

I would like to know whether we could pump $ba$ into $bbba$ where x=$b$,y=a,z=$\epsilon$ using the finite state machine given in the image 1. For example as given in this image 2 where the string ...
2
votes
2answers
73 views

Regular language? Union of the dictionary and an non-regular language

I'm attempting to figure out if a union of two languages is regular. $$ L_1 = \{all\ the\ words\ in\ the\ Oxford\ dictionary\} \\ L_2 = \{w : w\ has\ twice\ as\ many\ a's\ as\ b's\} $$ $L_2$ is well ...
-1
votes
2answers
56 views

DFA for $L_1={w:(n_a(w)+2n_b(w)) mod 3<2}$ and $L_2=\{w:(n_a(w)+2n_b(w))\text{mod 3}<2\}$

I stumbled upon this file on scribd, which gave some interesting problems on constructing DFA. So I went on solving them, until I came across one for which result DFA is not drawn but are described in ...