Questions tagged [regular-expressions]

Questions about regular expressions, a formalism to describe regular languages.

Filter by
Sorted by
Tagged with
3
votes
1answer
779 views

Simplifying regular expressions

This is the homework question: $ \{w \in \{a, b, c\}^* : \text{(no symbol occurs twice in succession in w)}\} $ This is my answer: $$\{((abc)^*| (acb)^*| (ab)^* | (ac)^*)^* | (bac)^* | (bca)^* |...
2
votes
2answers
187 views

Regular expression for binary words with few zeros

What is the regular expression for the set of binary strings with the property that every $0$ is followed by exactly $m$ times $1$ and every $0$ is preceded by at least $n$ times $1$? $m$ and $n$ ...
1
vote
2answers
230 views

Is there a name/interest for regular languages that have a non-ambiguous ending?

The basic idea is to have one or more symbol that clearly indicate the end. For example: Non-ambiguous: $ab^*c$ $(a|b)c$ $ab^+c$ $ab?c$ $a(b|c)$ $c(ab)^*ccc$ $acc^*d$ $abc|bcd$ ...
0
votes
1answer
172 views

What is meant by “give pattern of a regular expression”

I have an alphabet $A = \{b,B\}$ and I'm asked to write down the pattern of the regular expression $(\epsilon|bb|b)(B|bb)(b|\epsilon|b)$. What does the question actually want me to do? I'm not sure. ...
4
votes
2answers
298 views

Is this language regular or not?

$L_1=\{a^ku \mid u \in \{a,b\}^* $ and $u$ contains at least $k$ a's, for $k\geq 1\}$. If it is regular, I haven't found its regular expression or any closure property to prove it. If not, it seems ...
-1
votes
1answer
1k views

Formal Languages - Expressive power of Formalisms

I need help with the following question: Order the following formalisms according to their expressive power: placing A before B means that any language definable by A is definable by B. Also state ...
24
votes
1answer
594 views

“Dense” regular expressions generate $\Sigma^*$?

Here's a conjecture for regular expressions: For regular expression $R$, let the length $|R|$ be the number of symbols in it, ignoring parentheses and operators. E.g. $|0 \cup 1| = |(0 \cup 1)^*| ...
2
votes
1answer
62 views

I need to present a regular expression for the following languages:

1. L2 = E{0,1) All the words in L2 with equal number of 0's and 1's and every prex of w has at most two more of either 0's or 1's. 2. All words that does not contain “bbb” as substring. i think ...
1
vote
1answer
136 views

Does $(a \mid b)^*$ match $a^n$ and $b^n$?

I am getting confused by the regular expression $(a\mid b)^*$ as it for sure matches $aab$ and $ab$. Does $(a\mid b)^*$ also match strings like $aa$, $aaaa$, $bb$ or $bbb$, that is those that use ...
2
votes
1answer
3k views

Simplification of regular expression and conversion into finite automata

This is a beginners question. I and reading the book "Introduction to Computer Theory" by Daniel Cohen. But I end up with confusion regarding simplification of regular expressions and finite automata. ...
3
votes
2answers
92 views

Language member explanation

Given the following formal language $L$: $$ L=\{ww \mid w\in\{a,b\}^*\}$$ Why is $a$ not a member of this language? So what is $\{a,b\}^*$ exactly? I thought it means $(a+b)^*$?
0
votes
1answer
593 views

Program that generates a regular expression from an FA [duplicate]

Possible Duplicate: How to convert finite automata to regular expressions? Im curious if anyone knows if its possible to write a program to generate a regular expression given a finite automation....
16
votes
2answers
3k views

Are regular expressions $LR(k)$?

If I have a Type 3 Grammar, it can be represented on a pushdown automaton (without doing any operation on the stack) so I can represent regular expressions by using context free languages. But can I ...
6
votes
1answer
233 views

regular expression given the language

The language is: $$ L = \{ (a^n) (b^m) \mid n + m = 3k, k \ge 0 \} $$ My attempt at an answer: $$ (a \cup b)^{3k} $$ This will work if the a OR b can change for each instance in the string that is (...
1
vote
1answer
505 views

A regular expression for a given formal language

I wanted to ask if someone can help me to construct a regular expression over the alphabet $\{a,b,x\}$ for the language $L$ which is constituted by all strings containing an odd number of $a$'s, and ...
-1
votes
1answer
276 views

construct regular expression

I need help with the following exercise: Construct an $\varepsilon$-NFA for the following regular expression $(a|\varepsilon)(ba)^*(c^*a|bc)^*$. i already tried this exercise with nerode but i didnt ...
12
votes
2answers
2k views

Does the language of Regular Expressions need a push down automata to parse it?

I want to convert a user entered regular expression into an NFA so that I can then run the NFA against a string for matching purposes. What is the minimum machine that can be used to parse regular ...
3
votes
2answers
126 views

Regular Expression for the language that requires one symbol to occur at least once

I am trying to figure out the simplest way to do this using a regular expression. Three symbols a, b, c. The sequence length is unlimited, i.e. *. The symbol a must be somewhere in the sequence at ...