New answers tagged regular-expressions
1
The first language can be described as the set of words on the alphabet $\{a,b\}$ with an even number of $b$'s.
The second one is not the language of words on the alphabet $\{a,b,c\}$ with an equal number of $b$'s and $c$'s (this condition would define a non-regular language). You could use greybeard's description or say: the language contains the empty ...
1
For your specific question, you are asking to generate a string in $\bar{L} \cap P$. Note that since $L$ is regular, so is $\bar{L}$; and note that $P$ is context-free. It is known that the intersection of a regular and context-free language is context-free. So, you're asking: given a context-free language, how do we generate a word in that language? ...
1
As Rick Decker rightly noted, real-world lexical analysers produce a DFA with multiple final states.
Lexical analysers created via Lex-like generators differ from theoretical DFAs in several respects, and this is only one of them. Another obvious difference is that they don't stop at the end of the input string.
Instead, lexical analyser generators ...
2
You should look into Theory of Automata, Languages and Computation:
These are the theoretical foundations of scanning, parsing and processing text (and furthermore constructing formal languages and grammars).
Components of the theory, are, for example:
Pushdown automaton
Context free grammars
Parsing techniques such as recursive decent, LL or SLR parsing.
...
2
You need to distinguish between regular expression syntax and its interpretation aka semantics.
"$\lambda$" is a symbol representing the set that contains only the empty string $\{\varepsilon\}$).
"$\phi$"¹ is a symbol representing the empty set of strings $\emptyset = \{\}$.
The difference becomes apparent when you compute the interpretation $i$ of a ...
0
Why there is no way to write "permutation of" in Regexes
A permutation of a regular, infinite language (infinite amount of words) is not necessarily regular. Thus, it can't be written as regex.
Proof
Think of of the language (ab)*. (Example inspired by David Richerby.) One of its permutations is a*b*. This is not a regular language. qed.
Top 50 recent answers are included
