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

learn more… | top users | synonyms

0
votes
1answer
54 views

Proving $A$ avoiding $B$ regular if $A$ and $B$ are regular

Suppose we define an operation such that $$A \text{ avoiding } B = \{w \in A \mid w\text{ has no substring in }B\}\,.$$ How can I prove that, if $A$ and $B$ are regular then $A\text{ avoiding }B$ ...
0
votes
2answers
109 views

How do you find an infinite regular language that is a subset of a non-regular language?

In order to do this, we would probably need the non-regular language to be infinite as well, then find some definition for the non-regular language in order to fulfill the requirement, but I don't ...
0
votes
1answer
33 views

Proving following regular expressions equal to one another?

How would I go about proving the following two regular expressions are equal to one another: ( a + b )* a ( a + b )* b( a + b )* = (a + b)* ab(a + b)* I can ...
1
vote
1answer
29 views

Equivalence of regular grammars

I know that proving context free grammars equivalent is undecidable. I also know that proving if a context free grammar recognizes a regular language is undecidable. Here is my question: is proving ...
-1
votes
0answers
42 views

regular Language and nfa [closed]

please how to proof this proposition can you give me a way to a proof : let L be a regular language that does not contain epsilon.show that there is an nfa without epsilon-transitions and with a ...
0
votes
1answer
37 views

complement of a language-nfa

hi i know that the question 5 is true because by definition w ∈ L if and only if δ*(q0,w)∩F ≠ ∅. Consequently, if δ∗ (q0,w)∩F = ∅, then w ∈ L1. "L1 is the complement of L" but iam really confused ...
10
votes
3answers
2k views

Regular languages that can't be expressed with only 2 regex operations

I thought all regular languages could be expressed with regular expressions (if a language is regular, it can be expressed with regex), but I have been told that you need all three of the regular ...
0
votes
3answers
77 views

Finding a regular expression for all non-empty binary strings that contain both 0s and 1s but no consecutive 1s

This is for formal-language-style regular expression and not about Unix-style regular expression. I was trying to find the regular expression that doesn't accept empty string, doesn't accept strings ...
2
votes
1answer
41 views

Why is my regular grammar for palindromes wrong?

I've seen that people prove somehow that set of all palindromes isn't regular language by using a pumping lemma, which I am not familiar with. I've created grammar which can generate all palindromes ...
3
votes
1answer
39 views

Is the word problem for regular languages in ALogTime?

Given a regular language (by a sparse or dense matrix describing the graph of the NFA) (initially the description was supposed to be a regular expression) and a word, can the problem whether the word ...
3
votes
4answers
88 views

How to determine if a regular language L* exists

I'm trying to make sense of regular languages, operations on them, and Kleene operations. Let's say I define a language with the alphabet {x, y}. Let's further say that I place the restriction that ...
1
vote
2answers
80 views

Designing a DFA for binary strings having 1 as the fourth character from the end

I came across someone else's old post here Designing a DFA that accepts strings such that nth character from last satisfies condition And decided to try it. Apparently it was a homework problem but ...
-1
votes
1answer
35 views

checking if string is generated by regular grammar

How do I check wether a string is generated by given regular grammar? I know you can check for it in O(N), what is the algorithm called?
7
votes
3answers
144 views

DFA for accepting all binary strings of form power of $n$ (not divisible by $n$) i.e. $n^k$ for given $n$

We can form DFA accepting binary numbers divisible by $n$. For example DFA accepting binary numbers divisible by 2 can be formed as follows: Similarly DFA accepting binary numbers divisible by 3 ...
0
votes
1answer
52 views

Why is $L=wxw^R|w,x\in\{0,1\}^+$ regular? [duplicate]

I was taught that if you can create a DFA to accept a language, then the grammar that is generating the language is regular. AND A DFA is a finite automata that accepts a language and also rejects ...
0
votes
1answer
73 views

If a machine recognizes language L, can it also recognize L*?

This is a homework question. Suppose the only accept state is the start state. My rationale for this is that L* is just the concatenations of L, so if all strings in L are accepted, then all strings ...
8
votes
0answers
60 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 ...
3
votes
1answer
52 views

Does a DFA accept an empty string if $q_0$ is the accept state?

Suppose $q_0$ is the start state, does this mean that if it's the accept state, then the machine must accept the empty string since it cannot have a transition with the empty string?
-3
votes
1answer
41 views

The language of all base-10 integers that are multiples of 9 [closed]

If I want to represent all the base 10 integers that are multiples of 9 as a language how do I do so? Alphabets are finite sets.
-4
votes
2answers
60 views

Are all irregular languages infinite?

How can I prove whether irregular languages are infinite? I thought about proving it by the definition of regular language but got stuck.
1
vote
1answer
41 views

why DFA to regex by two different methods differ

I was learning converting DFA to regex. I came across Arden's method which solve given DFA as follows: Ardens method Let us form the equations $q_1 = q_10 + q_30 + є$ $q_2 = q_11 + q_21 + q_31$ ...
-3
votes
1answer
32 views

Step by step method for generating Regular Expressions for languages [duplicate]

I was wondering if there was a method that can be used to generate a Regular Expression for a language. Take the Language $L$ as an example where: $L= \{w \in \{0, 1\}^{\ast} \mid \text{length of } w ...
1
vote
3answers
72 views

DFA for w|w has a length multiple of 2 or 3 [duplicate]

I am trying to create a DFA and a regex for this kind of exercise: $A = \{w ∈ \{0, 1\}^* |\text{length of w is a multiple of 2 or 3}\}$. I tried to do one for $2$ and one for $3$ and then combine ...
2
votes
1answer
98 views

Grammar of regular languages vs. context free languages

Let $L$ be some language. What could you say about $L$'s grammar if it is a regular language, that couldn't be said if it was a context free language? For example, in case $L$ is regular, could you ...
3
votes
0answers
36 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?
2
votes
1answer
45 views

Using Context free language to simulate regular expression in finite automata

Is there a minimum number of non terminal we need to use in order to simulate a finite automata with n states? When we try to convert a language accepted by NFA to context free language, do we need n ...
-1
votes
1answer
27 views

Unambiguous CFG that generates regular language according to Pumping Lemma?

The pumping lemma for regular languages states: Specifically, the pumping lemma says that for any regular language L there exists a constant p such that any word w in L with length at least p can ...
5
votes
1answer
69 views

Show that some context free languages must contain more that one non-terminal

Context free languages that has only one non-terminal is a proper subset of context free languages and they does not contains regular set. Since, CFL is more powerful than FSM and contains regular ...
5
votes
1answer
51 views

Algorithm to find a minimal regular language containing given context-free language

I am not sure that the problem is in general solvable, but here's an example of what I mean: Any context-free language has a trivial regular language that contains it: $\Sigma^*$. The language ...
1
vote
1answer
42 views

Proving that language, with $|\Sigma|=1$, is irregular by Myhill–Nerode theorem

We have $\Sigma =\{0\}$ and $$L=\{0^{2^n} \mid n\ge 0\}$$ How to prove that $L$ is irregular by using Myhill–Nerode theorem? At other languages with $\Sigma >1$ we can usually separate the word or ...
0
votes
1answer
92 views

Proving that two sets of strings are equal

I am stucked at this problem: Let $A=(\Sigma, Q, q_1, F, \delta)$ be a finite deterministic automaton (I.e. $\delta:Q\times\Sigma\to Q$) such that $Q=\{q_1,...,q_m\}$. Let's define foreach ...
2
votes
2answers
143 views

Is {wxw^r} a regular language?

Is $\{ WxW^{\mathrm{R}} \mid W,x\in\{0,1\}^+\}$ a regular language? If so, why? The notation $W^{\mathrm{R}}$ means the reverse string of $W$? If we consider the best answer in this solution, ...
0
votes
0answers
33 views

How to prove that the language of words ucv with as many a's in u as b's in v is irregular?

I'm trying to prove that: $L=\{w\in\{a,b,c\}^*\Big|\#_a(u)=\#_b(v),\ \ w=ucv,\ \ \ u,v\in\{a,b\}^*\}$ is irregular, so I'm trying to use the Pumping Lemma. This is what I tried so far: ...
-1
votes
1answer
63 views

Language of Palindrome-Prefixed Words

Classify the language $L = \{xx^Rw\ \big|\ (|x| \geq 0\ \wedge |w|\gt 0)\ where\ x,w\in\Sigma^*\}$ as one of: Regular but not Context-Free Context-Free but not Regular Decidable ...
4
votes
2answers
127 views

Pumping lemma: if you can keep pumping, what does this tell you?

Hypothetically, let's say you are using the pumping lemma for either regular or context free languages. Now using either, you come across a case that remains true despite pumping it. In this ...
-1
votes
1answer
44 views

“Best” automaton for a regular language

For a given regular language, there are multiple finite automata. How do we determine which one is best?
0
votes
3answers
85 views

Why is $\{1^n \mid n > 1\}$ regular?

Given the definition of a regular language is one that can be expressed with finite memory, how is $\{1^n \mid n \geq 1\}$ regular? The $n$ is unbounded. I know a DFA can be drawn, which means the ...
1
vote
1answer
49 views

Regular languages closed under quotients with arbitrary languages

When proving that that the quotient of a regular language $R$ and an arbitrary language $B$, I understand you take a DFA $M$ accepting $R$, and then construct a DFA that is the same, but its final ...
-1
votes
1answer
31 views

Algorithm that deside if there are two words $x$ and $y$ in the same length such that $x\in L(A_1)$ and $y\in L(A_2)$

Let $A_1=(Q,\Sigma,q_0,F_1,\delta _1)$ and $A_2=(P,\Sigma ,p_0,F_2,\delta _2)$ a finite non determinustic automaons. Describe algorithm that deside if there are two words $x$ and $y$ in the same ...
0
votes
1answer
41 views

k-tape turing machine

I want to create multi-tape Turing machine that recognize language {ww, $w \in {a,b}$}. With condition that max. steps is less or equal than $\frac{3}{2}\left | x \right | + 2$. Where x is word from ...
0
votes
3answers
36 views

Difference in having * inside vs outside of brackets for NFA

If you have a question saying "draw the NFA for the following language" what difference does it makes if the language is $(0^* \cup1^*)$ vs $(0 \cup1)^*$ in otherwords what difference does it make for ...
1
vote
1answer
55 views

Proving specific prefixes of regular languages are regular

There are particular problems in Kozen that I'm unable to solve, and they seem to be similar to each other. It is showing that sets: $$ \{x \mid \exists y: |y| = 2^{|x|} \text{ and } xy \in A \}$$ $$ ...
2
votes
1answer
44 views

How to prove that $L_1=1^*\cup \{0^i 1^{j^2}|i\ge 0,j\ge 0\} $ is irregular? [duplicate]

We know that $L=\{0^i 1^{j^2}|i> 0,j\ge 0\} $ is irregular (by the Pumping Lemma), we have to use it to prove two things: $L_1=1^*\cup \{0^i 1^{j^2}|i\ge 0,j\ge 0\} $ is irregular. $L_1$ is ...
0
votes
3answers
51 views

Why does it seem as if I can apply the Pumping lemma to a language that is regular?

We learn about the Pumping Lemma at the class and I tried to make few examples to understand it... There I make this example: Let's say: $L=\{w\in L|w=(0+1)^*1\}$ - i.e. - L is the language of all ...
2
votes
1answer
65 views

Find a regular language that is “infinitely between” two other regular languages

Suppose I have two regular languages $L_{1}$ and $L_{2}$ such that $L_{1} \subseteq L_{2}$ and $L_{2} - L_{1}$ is infinite. I want to find another regular language $L_{3}$ such that $L_{1} \subseteq ...
1
vote
0answers
38 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 ...
8
votes
4answers
139 views

If $L_1L_2$ is regular language then $L_2L_1$ is regular to?

We have two languages: $L_1,L_2$. We know that $L_1L_2$ is regular language, so my question is if $L_2L_1$ is regular to? I try to find a way to prove it... I can't assume of course that $L_1,L_2$ ...
2
votes
1answer
57 views

Meaning of $\stackrel{*}{\rightarrow}$ production rule?

I've seen the production rule $\stackrel{*}{\rightarrow}$ in some papers concerning regular languages. What's the meaning of $\stackrel{*}{\rightarrow}$ production rule?
0
votes
1answer
106 views

Languages that are not subset, but are union

Are there examples of regular languages $L_1$ and $L_2$, where $L_1$ and $L_2$ is not a subset of each other but that $(L_1 \cup L_2)^* = L_1^* \cup L_2^*$ ?
2
votes
1answer
137 views

∅-free regular expressions?

This is a question involving regular expressions for regular languages. I am currently stuck trying to prove that the operand ∅ is not necessary unless the language is the empty set. That is, a ...