# Questions tagged [regular-languages]

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

1,427 questions
Filter by
Sorted by
Tagged with
29 views

### Over every non-empty alphabet there exist languages which are non-regular

I am not sure about the answer. Intuitivly I would say that there are alphabets for which there are no non-regular languages. In particular I am thinking of languages with only one element. But I am ...
18 views

### State machine to convert from base 2 to base 10?

Is there a state machine which can convert base 2 decimals to base 10 decimals in a streaming fashion? Integers?
24 views

### Construct a CFG for $L = \{ w \in \{0,1\}^*\text{ } |\text{ } w = w^R \text{ and } |w| \text{ is even}\}$

I need to construct a CFG for the following language$$L = \{ w \in \{0,1\}^*\text{ } |\text{ } w = w^R \text{ and } |w| \text{ is even}\}$$ I know that the two middle position should always be the ...
33 views

Given an unambiguous context-free language L and an unambiguous regular language L (moreover, every regular language is unambiguous) such that L∩ R = ∅, then prove that L∪ R is also unambiguous.
24 views

### Create an Finite Deterministic Automata for a regular expression

I want to create a finite state machine that accepts the following language: $$L=\{w\in\{a,b\}^* | w \text{ contains abb but not on the first position}\}$$ So I began by writing a regular expression ...
58 views

### Proving some subsets of a regular languages to be regular languages

I have to prove that if a language $L$ is regular then: a) $NONPREFIX(L)=\{u \in L /$none of the prefixes (not $\epsilon$ or $u$) of $u$ are elements of $L \}$ is regular On this one I think I can ...
24 views

### How do i prove this language is regular? [duplicate]

I have this language {0+1+0+} and i need to prove it is regular,i had the idea to use the closure properties but i can find any regular languages to unify perhaps.Any ideas?
54 views

### How can I show that this language is context sensitive?

I have this language $L=\{a^nb^nc^n,n\geq0\}$, I know this language is not context free, but I don't know how to show that it is context sensitive, do I have to use a PDA?
42 views

### Is this language based on the number of $a$'s of a word over alphabet ${a, b}$ context-free?

I'm trying to use the pumping lemma, to show that the language $L = {w \in \{a, b\}^+: na(w) = nb(w)}$ is not context free, where $na(w)$ is the number of $a$'s in $w$. I have this: By contradiction, ...
31 views

### How to check if a language is not regular?

I have the given regular language and i am suppose to check if it is regular and if it is, to provide a regular expression However, if the language is not regular i have to prove using the "...
17 views

### Relationship between Kleene Star of a subset of regular language and the regular language

If $L(R_1) \subseteq L(R_2) \subseteq L(R_3)$ then $L(R_1)^* \subseteq L(R_2)^* \subseteq L(R_3)^*$. Does this also imply that $L(R_1)^* \subseteq L(R_3)$?
53 views

### What are the most used statements in programming (ranked)?

I was wondering if there are any resources for a study/ranking of the most frequently used statements (by statements I mean assigning, invoking, instantiating etc, like in C#) in programming overall (...
19 views

### is the intersection of a context free language and a regular language a two way street?

I wasn't sure how to word it correctly, hence the 'two way street' in the title. My question is: The intersection of a context-free language and a regular language always results in a context free ...
21 views

### Are regular grammar languages defined from “accepting” states?

In a transition diagram, the language L(D) where D is the diagram is defined as all the words that are formed from following an "accepting" walk. Does the same apply for languages of regular ...
34 views

### Regular expression for all binary words avoiding 11

I am reading a book example on regular expressions and I have a trouble to get why the answer is correct. "Write a regular expression for the regular language that contains all the strings by 0's ...
74 views

### Language of all even-length words with no 1's in left half

Consider the following language: $$L=\{w \in \textstyle\Sigma_1 ^*\mid|w| \text{ is even and 1's can only occur in the second half of w}\},$$ where $\Sigma_1 = \{0,1\}$. I need to show that this is ...
22 views

### All string matches for regular expression [duplicate]

Given a regular expression, the ask is to find all matches in a string, str. Most implementations give longest match only. For example, [\d]* in str "123456", the regex libraries in C++ or ...
32 views

### Regular language is closed given transposition of rightmost character to leftmost

It would appear straightforward to show that a regular language is closed given the transposition of the rightmost character to the front. However after drawing a few sample DFA for the phenomenon, I'...
35 views

### Irregularity of $\{a^x b^y c^z : x=2y \lor y>z\}$

Show that $L=\{a^x b^y c^z : x=2y \lor y>z\}$ is not regular using the pumping lemma. I know that in order to use the pumping lemma, I have to assume that $L$ is regular. Then I know that there is ...
20 views

### Is there a direct way to obtain the RE for the handle-finding DFA of a grammar?

LR parser for a (CFG) grammar uses a handle-find automaton (which is a DFA) to find the handles. Such automata can be constructed by computing the canonical collection of sets of LR(0)/LR(1) items. Is ...
14 views

### Is that a regular express? Proof using closure properties or pumping theorem [duplicate]

I am studying regular express. I understand how to proof a xa ya. However, I don't know how to proof the below problem. Please help me. L = { xa yb | a ≠ b }
31 views

### Is (a+b)* and (ab)* same in finite automata?

Regular language of (a+b)* and (ab)* are: (a+b)* = { ε, a, b, aa , ab , bb , ba, aaa, ...} (ab)* = { ε, a, b, aa, ab, ba, bb, aaa, ... } I am new to Finite automata and this simple notion is ...
140 views

### Does O(1) communication complexity imply that a language is regular?

Let's say that we have a function $g(i,j)$, which is an arbitrary boolean-valued function over $i,j \in \{a,b\}^*$, such that $|i| = |j| = m.$ Moreover, we can also say that $g$ has communication ...