Questions tagged [regular-languages]

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

Filter by
Sorted by
Tagged with
1
vote
0answers
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 ...
0
votes
0answers
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?
2
votes
1answer
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 ...
0
votes
1answer
33 views

Can someone please help with the proof of this?

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.
0
votes
1answer
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 ...
1
vote
2answers
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 ...
0
votes
1answer
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?
2
votes
1answer
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?
1
vote
1answer
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, ...
0
votes
1answer
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 "...
0
votes
1answer
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)$?
2
votes
1answer
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 (...
1
vote
1answer
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 ...
1
vote
1answer
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 ...
0
votes
0answers
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 ...
1
vote
2answers
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 ...
0
votes
0answers
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 ...
1
vote
2answers
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'...
0
votes
1answer
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 ...
1
vote
0answers
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 ...
0
votes
0answers
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 }
0
votes
1answer
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 ...
4
votes
2answers
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 ...
0
votes
2answers
33 views

What does this language notation specify?

I am given this exercise: Let L1 ={akbk : k > 0} and L2={ck : k > 0}. For each of the following strings wi, state and explain whether or not wi ∈ L1L2. w1=ε w2=aabbcc w3=abbccw w4=aabbcccc w5=...
1
vote
2answers
33 views

Proving a language with equal occurences of ab, and cd is not a regular language using the Pumping Lemma

I am trying to show that $A = \{w \in \{a,b,c,d\}^{*}|w \textrm{ has equal occurences of } ab \textrm{ and } cd\}$ is not regular by using the Pumping Lemma. My idea here was to use the string $ s = (...
1
vote
1answer
31 views

Applying the Pumping Lemma to aspecific string

Given the language $ A = \{w \in \{a,b\}^{*} | w = w^{R}\}$ (i.e. palindromes using the symbols $a, b$), I am trying to determine if the Pumping Lemma can be applied to strings of the form $s = a^{2p}$...
0
votes
2answers
22 views

string concatenation vs language concatenation

What exactly is the difference between $$ C = \{a^*\}\{b\}\{a^*\}\{b\}\{a^*\}\{b\} $$ and $$ D = \{a^nba^nba^nb | n \geq 0 \} $$ It is known that D is non-regular and C is regular, but I am not sure ...
2
votes
2answers
37 views

How to we prove if a right linear language is ambiguous?

Considering the following language as an example: $$\begin{align} S &\rightarrow aS \mid bA \\ A &\rightarrow bA \mid aB \mid aD \mid \varepsilon \\ B &\rightarrow aB \mid \varepsilon \\ D ...
0
votes
1answer
33 views

Read regular Expression from NFA

Good evening everyone! Can someone help me with the following task? So we have this NFA: I was supposed to create a regular expression out of it. Now the solution says: $a^{+}b^{+}(c|ca^{*}b^{+})^{*}$...
0
votes
1answer
110 views

What is the the pumping length for the regular expression (0+0001)((1111)*+(00)*)

I have this assignment question to find the pumping length of a regular language (L). The regular expression for the L is given as $(0+0001)((1111)^*+(00)^*)$ What is the length of the longest string ...
0
votes
0answers
15 views

Constructing a context free grammar with starting state

I'm supposed to construct a context-free grammar generating all strings in : {(ab)$^{m}$c$^{n}$(ba)$^{m}$ : m, n, ≥ 0} So far I have V = {A, S, a, b, c}, Σ = {a, b, c}, and R = (1) S -> A (2) S -&...
2
votes
1answer
36 views

Is “A -> aAA” convertible to regular grammar?

I have a simple grammar as below and wonder if it is convertible to regular grammar? If yes, what is the conversion sequence? If no, how can we prove it? ...
0
votes
1answer
24 views

minimum number of states in cross product of two minimum DFAs

If FA1 and FA2 are 2 DFAs with minimum number of states. I want to find cross product DFA (FA1XFA2). Will the cross product DFA obtained from 2 minimum DFAs also have minimum number of states(num of ...
-1
votes
1answer
25 views

Proving of regular language [duplicate]

Is this regular or not L = {w1w^R | w ∈ {0,1}* (where for any word w ∈ {0,1})*, w^R denotes the reverse of w)
1
vote
2answers
58 views

How to prove that concatenating a language A and A* is commutative?

Suppose we have a language $A$. I want to prove that $AA^*$ is commutative. I know that this expression equals $A^+$, but I'm not sure how to go about a proof yet. This is my attempt so far. If $A$ is ...
0
votes
0answers
86 views

Generalization of automaton - Sipser example 1.33

I am trying to construct a nfa that generalizes Example 1.33 found in the book Introduction to the Theory of Computation by Sipser, but I am quite sure that my transition function is wrong. I'd like ...
6
votes
1answer
1k views

Is it possible to build any regular expression in a computer language with just 3 basic operators?

Many computer languages have complex regular expressions tools. For example, in Javascript you have global flags, escape characters, whitespace character, assertions, character classes, groups and ...
1
vote
2answers
14 views

PDA for a language where the second part is not the reverse of the first part

I came across an exercise for constructing a PDA for the following language: $$L = \{ncm \mid n,m\in\{a,b\}^* \text{ and } n \ne m^R\}.$$ Where $L \subseteq ({a,b,c})^*$ So $n$ and $m$ are both a ...
0
votes
0answers
24 views

Regular expressions accepted by programming languages but are not regular [duplicate]

The below definition of Regular Language is given in Wikipedia. In theoretical computer science and formal language theory, a regular language (also called a rational language) is a formal language ...
1
vote
1answer
19 views

A regular language derived from another

This is similar to a previous question I asked, but doesn't seem aminable to the same technique. Given a regular language $A$, show the following language is regular: $$ \{x|\exists y \; |y| = 2^{|x|} ...
0
votes
1answer
35 views

Can this language be called regular?

Recently, I was facing some problems in effectively proving the following : Consider the alphabet Σ ={0,1,2,...,9,#}, and the language of strings of the form x#y#z, where x,y and z are strings of ...
0
votes
2answers
70 views

How can I efficiently construct a CFG from a language

I am new to CFG's and automata in general and I came across an exercise where I needed to construct a CFG for the language {a^m b^n | n <= m + 3}. So m can be infinitely bigger than n but n can ...
1
vote
1answer
31 views

Regularity of a language constructed from a know regular language

I'm working through so textbook questions on regular languages, and came across a problem that amounts to showing the following language is regular, given that $A$ is a regular language: $$ \{x|\...
0
votes
2answers
82 views

How to understand and apply pumping lemma to prove $a^{i+1} b^{4i+2}$ is not regular?

I am having trouble understanding how to apply Pumping Lemma to show a Language is not regular. If the alphabet is $\Sigma = \{a, b\}$ and the language is $L = \{a^{i + 1} b^{4i + 2} \mid i \in \...
0
votes
1answer
39 views

How to apply Arden's theory to determine a regular expression

If $P=ab$ and $Q=a^*$, how do I use Arden's theorem to determine the regular expression $R$. I'm not sure if I am supposed to just substitute the values of $P$ and $Q$ in the equation $R= Q + RP$. ...
1
vote
1answer
28 views

Construct a DFA recognizing a language $L$ that has exactly $I(L)$ states

Let $L$ be a language, and consider the following relation $\equiv_L$ on strings: $s_1 \equiv_L s_2$ if and only if, for every string $w$, we have that $s_1w \in L \Leftrightarrow s_2w \in L$. This is ...
0
votes
2answers
41 views

Can a regular expression be any string from the language described by it? [closed]

Is it possible to have a regular expression from a language (that has strings of infinite length) which it describes ?
2
votes
2answers
47 views

Proving non-regularity via syntactic congruence classes?

Let $L$ be a language. The Myhill-Nerode theorem is based on the following equivalence relation: $$x \equiv_M y \Leftrightarrow \forall v \in \Sigma^*. (xv \in L \leftrightarrow yv \in L).$$ One ...
3
votes
0answers
37 views

BNF rule to regular expression

I'm looking for a way to find out whether a specific rule in a BNF grammar can be converted to a regular expression. (With "regular expression" (RE), I mean the simple mathematical kind. I'm ...
1
vote
1answer
119 views

Check if a NFA accepts a string of non-prime length

Given a nondeterministic finite automaton $A$, give an algorithm that checks whether the language $L(A)$ decided by $A$ contains a string whose length is a composite (i.e. not prime) number. My ...

1
2 3 4 5
29