Questions tagged [regular-languages]

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

130 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
0
votes
0answers
288 views

Regular language with number of a's same as number of b's

L = { x^n y^n / x,y belongs to (a+b)^* , number of a's in x = number of b's in y and n > 0} According to me it's regular because for any string $w$ belongs to $(a+b)^*$, we can divide the string into ...
0
votes
0answers
92 views

Does this grammar generate regular language?

$S \rightarrow AB$ $A \rightarrow aA \mid bA \mid \epsilon$ $B \rightarrow aBb \mid \epsilon$ Does this grammar generate regular language? According to me this grammar generates language of the ...
0
votes
0answers
62 views

proving L = {$a^{100}yy^r : \forall y \in$ {a,b}*} is not regular

I need to prove that L = {$a^{100}yy^r : \forall y \in$ {a,b}*} is not regular. i have tried using pumping lemma but couldn't get far with it. Any help in where i should go with it?
0
votes
0answers
833 views

Proof of every regular language has a LL(1) grammar

I tried some examples and found that LL(1) grammar always exist. I tried searching for formal proof but didn't find any. Can someone give a formal proof for the above statement?
0
votes
0answers
24 views

Operation on languages results in CFL

For every two languages $L_{1}$ and $L_{2}$ over the alphabet $\{ a,b,c,d \}$, we define the language $$L_{1} \operatorname{op} L_{2} = \{ \alpha\beta \mid \text{$\alpha \in L_{1}$ and $\beta \in L_{...
0
votes
0answers
305 views

Inverse Homomorphism expression

Consider the following expression :- $$h(h^{−1}(L))$$ I need an example where this expression can be superset of subset of L,but i am not able to get one.I am getting this equal to L always.How can ...
0
votes
0answers
110 views

Is there some problem in “promise-DSPACE(o(log log n))” that is also in “promise-DFA”?

Disclaimer I have no idea about complexity theory. If this question makes no sense or is wrong, mods are free to delete the question I´ve read somewhere that the problems that can be correctly ...
0
votes
0answers
31 views

Valid parenthesis Matching in MSO

What is the Monodic Second Order formula that encodes all binary strings that represent a valid parenthesis matching ? By this I mean 1s represent '(' and 0s represent ')' and at every position, ...
0
votes
0answers
48 views

Prove or refute that language $L=\{a^{n}b^{m}c^{{m}\choose{n}}\}$ is regular

I'm little confused with proving if this language is regular: $L=\{a^{n}b^{m}c^{{m}\choose{n}}\}$. What are $n,m$? Are they arbitrary? If yes, this language has only one word and I need to prove or ...
0
votes
0answers
318 views

Writing a constructive proof for closure of a regular language under homomorphism

I've spend the last few days searching online for an example of a constructive proof of regular languages being closed under homomorphism, but I have not seen one. I am mostly unsure of how to show ...
0
votes
0answers
35 views

Regular language is generated by clear grammar

Given a regular language , how could we prove that it is alsways ( or can be always ) generated by clear grammar ( such as that for every sentence exists only one derivation tree ). Could we prove it ...
0
votes
0answers
985 views

Can any left recursive grammar be converted into equivalent right recursive grammar and vice versa

I know how to convert any Left Linear Grammar (LLG) to Right Linear Grammar (RLG) and vice versa. This can be done as follows: Reverse "LLG for L" to get "RLG for LR" by changing A → Ba to A → aB ...
0
votes
0answers
123 views

Find a minimal regular expression for the languge of the words that does not contain bbb

Let's say my dictionary is {a,b} I want to ccind a regular expression for the languge of the words that does not contain bbb in the most minimal way. All I can think about is '+'ing between prefixes ...
0
votes
0answers
101 views

Prove that language is not regular using pumping lemma

Could anyone tell me If I can prove regularity of given language using pumping lemma like I did below? If my prove is wrong could anyone tell me how to prove that the language is not regular using ...
0
votes
0answers
101 views

Deciding the language of DFAs accepting $(101)^*$

I want to prove that $L = \{\langle T\rangle\mid T \text{ is a DFA and $L(T)$=$(101)^*$}\}$ is decidable. I have the following idea in mind: I design a TM $M$ such that, first of all, $M$ converts $...
0
votes
0answers
52 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 ...
0
votes
0answers
68 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: $w=a^ncb^n$...
0
votes
0answers
123 views

Making a regular grammar for this language

I'm trying to make a regular grammar for this language: Where the alphabet is $ \Sigma $ = $\{a,b,c\}$ It seemed like it would go well with a right-linear grammar. This may be disastrously wrong, ...
-1
votes
1answer
32 views

How to choose word for pumping lemma for $a^kb^{2k}a^k$?

I have to show that the language $ \mathcal {L} = \{a ^ k b ^ {2k} a ^ k: k \geq 0 \} $ is not a regular language. So that's what I want to use the pumping motto for. What I could do is this: let $ \ ...
-1
votes
1answer
51 views

Set-theoretic difference of two languages in CFL - REG

Let $L_1,L_2\in$ CFL $-$ REG, with $L_1\subset L_2$. Which of the following always holds? $L_1-L_2\in$ CFL $-$ REG and $L_1-L_2\in$ REG. $L_1-L_2\in$ REG and $L_2-L_1\in$ CFL $-$ REG. $L_1-L_2\in$ ...
-1
votes
1answer
17 views

Show that $R^{+} \equiv R \leftrightarrow L(RR) \subset L(R)$

Show that $R^{+} \equiv R \leftrightarrow L(RR) \subset L(R)$ sigma is any alphabet. R is a regular expression. How can L(RR) even be a subset or equal to L(R)?
-1
votes
1answer
567 views

How to convert a CFL to a deterministic PDA?

I am trying to complete this question. However, I am unsure of the steps necessary to complete the conversion from a CFL to a deterministic PDA. I know that $ww' | w \in \left \{ a,b \right \}^{*}, w'...
-1
votes
1answer
54 views

Regular Expression Building

I'm having trouble constructing a regular expression to meet the following criteria: $$\sum = \{0,1\}$$ $$\epsilon \in L$$ $$0 \in L$$ $$1 \in L$$ $$\forall x \in L, 110x \in L \land x01 \in L$$ ...
-1
votes
1answer
50 views

Intersection between language and regular set

This is tangentially related to a question I asked on the math stackexchange. I read in a proof that if $$ \begin{align*} L_1 &= \{w ∈ \{a, b, c\}^* : \text{$w$ has the same number of $a$, $b$, ...
-1
votes
1answer
2k views

Determining whether a context-free language (CFL) described by a given grammar is regular (RL)

In my homework we're given the following problem: Determine whether the context-free language described by the following grammar is regular, showing all the reasoning steps: S -> T T | U T -> 0 T | ...
-2
votes
1answer
412 views

Kleene star of L

$L^*$ is the kleene star of L. say we have a def: $L^*$ = $L^0$ U $L^1$ U $L^2$ U ... U $L^K$ then prove that: $L^*$ = $L$ if and only if $L$ = $L$ o $L$ how do i prove this?
-2
votes
1answer
1k 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 ...
-2
votes
1answer
357 views

Prove that $(L^*M^*)^* = (L\cup M)^*$

I would like to find out how to prove this statement. Thank you. Well I think that I proved one part of the statement, but my proof doesn't really look elegant. My proof of $(L\cup M)^* \subset (L^*M^...
-2
votes
1answer
13k views

Regular expression for all strings with at least two 0s over alphabet {0,1}

My answer : (0+1)* 0 (0+1)* 0 (0+1)* Why is this incorrect? Can somebody explain to me what the correct answer is and why?
-3
votes
1answer
44 views

Construct regular expression for given language

How to construct regular expression for language L={a,b,c} which contain all words starts with bab and ends with babc?

1 2
3