Regular Expression Kleene Star application – using 0s and 1s

Have a question from an online course I am trying to take for a certificate. Came across a few questions like this and need help working through the problem and the rationale to get the solution. Any help appreciated.

Consider the regular expressions R1 = (01)*(0*1*)(10) and R2 = (101)(01). Which of following is true?

10 in R1 and 101 R2

10 in R1 and 1000 R2

010 in R1 and 100 R2

010 not in R1 and 100 not in R2

Kleene star operations

Let $ 𝚺$ be any alphabet and let $ 𝑳_𝟏 \subseteq 𝚺^{∗}$ and $ 𝑳_2 \subseteq 𝚺^{∗}$ be two non-empty languages.

a. If $ 𝑳_𝟏 𝚺^{∗} \neq 𝚺^{∗}$ than what can we say about $ L_1$ .

b.Let $ \Lambda \in L_1$ and $ \Lambda \in L_2$ . Show using axioms and theorems of languages that $ 𝑳_𝟏 𝚺^{∗}𝑳_2 = 𝚺^{∗}$

For (a), $ \Lambda$ should not belong to $ L_1$ but I do not know how to prove that.

For (b),we have to prove that $ 𝑳_𝟏 𝚺^{∗}𝑳_2 \subseteq 𝚺^{∗}$ and $ 𝚺^{∗} \subseteq𝑳_𝟏 𝚺^{∗}𝑳_2$ for equality to exist. We can also distinguish two cases, when $ L = \Lambda $ , then $ \Lambda 𝚺^{∗} \Lambda = 𝚺^{∗}$ , but how can we prove that when $ L \neq \Lambda $

Any idea

Is there a polynomial-time algorithm to minimize regular expressions without Kleene closures/stars?

I have read that minimizing regular expressions is, in general, a PSPACE problem. Is it known whether minimizing regular expressions without the Kleene closure (star, asterisk) is in P?

The language of any such regular expression would be guaranteed to be finite. I suppose an equivalent question is whether the problem of constructing a minimal regular expression from a known finite language is any easier than minimizing an arbitrary regular expression. It seems like this should be the case.

(If the answer is that it is easier and there’s an obvious proof, I’m happy to go attempt it, I just haven’t thought about the problem deeply yet and wanted to see what I’d be getting myself into first.)

Kleene Star regex question, sed behavior?

Kleene Star with ‘sed’ is behaving as expected for me, with exception of a case where the input pattern is “ab” and the regex is “b*”. Does anyone know why this regex is not being matched against the pattern space?

This is the failure case:

$   printf "ab\n" | sed -En 's/b*// p' | od -t c 0000000   a   b  \n 0000003 

This case, without Kleene Star, behaves as expected:

$   printf "ab\n" | sed -En 's/b// p' | od -t c 0000000   a  \n 0000002 

I’m trying to match the ‘b’ and replace it with nothing.

The pattern space is ‘ab’, beginning of line is unspecified, so I’m confused why /b*/ would not match a pattern of zero or more ‘b’s, in this case ‘b’.

Oddly, this case works with the ‘.’ prepended to the ‘*’:

# fails to match $   printf "abb\n" | sed -En 's/b*// p' | od -t c 0000000   a   b   b  \n 0000004 # matches with .* ! $   printf "abb\n" | sed -En 's/b.*// p' | od -t c 0000000   a  \n 0000002 

Kleene Star matches zero or more occurrences of the preceding alphabet (in this case a single character).

By definition:

$ V^0 = \{\epsilon\}$

$ V^1 = V$

$ \forall i ( (i \gt 0) \land (V^{i + 1} = \{ wv : w \in V^i \land v \in V )\} $

Therefore $ V^0 = \{ \epsilon\}$ , $ V^1 = \{ \epsilon \cdot b\}$ , $ V^2 = \{ \epsilon \cdot b \cdot b\}$ .

$ V^* = \bigcup\limits_{i\ge0} V^i = V^0 \cup V^1 \cup …$ which I have specified by /b*/.

The following cases agree with my understanding of sed and Kleene Star:

# * : matches 0 or more occurances # no match $   printf "a\n" | sed -En 's/b*// p' | od -t c 0000000   a  \n 0000002  # match a printf "a\n" | sed -En 's/a*// p' | od -t c 0000000  \n 0000001  # match a printf "ab\n" | sed -En 's/a*// p' | od -t c 0000000   b  \n 0000002  # match aa printf "aab\n" | sed -En 's/a*// p' | od -t c 0000000   b  \n 0000002 

I tested using BSD and GNU sed, both have the same results.


Kleene star of a context-free language

Recently I had a question on one of my assignments asking to prove or disprove the following:

Let $ L$ be a language. If $ L^*$ is context-free then $ L$ is context-free.

Now obviously this is false since we can take some non-context free language $ L_1$ and the alphabet $ \Sigma$ , then make $ (L_1 \cup \Sigma)^* = \Sigma^*$ is context-free and clearly $ L_1\cup \Sigma$ is not.

Now I was thinking about a similar problem but now with respect to the words in the language, and was wondering if it is true or not. If $ C$ is a context-free language then $ C’$ is a context-free language where $ w\in C’$ if and only if $ w^*$ is contained in $ C$ .

My suspicion is that this is also false, but I can’t come up with a counter example. Somehow one needs to construct a CFL $ C$ such that the subset of all the “periodic” words of $ C$ together are not context-free.

Kleene realizability in Peano arithmetic

For completeness of MathOverflow and for clarity of the question, I will first recall a few things, including the the definition of Kleene realizability: experts can jump directly to the question below.

For natural numbers $ n$ and first-order formulae $ \varphi$ of Heyting arithmetic, the formula “$ n$  realizes $ \varphi$ ” is defined by induction on the complexity of $ \varphi$ by:

  • for atomic $ \varphi$ , “$ n$  realizes $ \varphi$ ” simply means $ \varphi$ [is true],

  • $ n$  realizes $ \varphi\land\psi$ iff $ n=\langle p,q\rangle$ (some fixed primitive recursive bijective pairing function $ \mathbb{N}^2\to\mathbb{N}$ ) where $ p$  realizes $ \varphi$ and $ q$  realizes $ \psi$ ,

  • $ n$  realizes $ \varphi\lor\psi$ iff $ n=\langle 0,p\rangle$ where $ p$  realizes $ \varphi$ or $ n=\langle 1,q\rangle$ where $ q$  realizes $ \psi$ ,

  • $ n$  realizes $ \varphi\Rightarrow\psi$ iff for each $ p$  which realizes $ \varphi$ , the value $ \{n\}(p)$ (of the $ n$ -th partial recursive function applied to $ p$ ) is defined and realizes $ \psi$ ,

  • $ n$  realizes $ \exists x.\psi(x)$ iff $ n=\langle k,q\rangle$ where $ q$  realizes $ \psi(k)$ (meaning the substitution for $ x$ in $ \psi$ of the explicit term representing the integer $ k$ ),

  • $ n$  realizes $ \forall x.\psi(x)$ iff for each $ k$ , the value $ \{n\}(k)$ is defined and realizes $ \psi(k)$ .

This in turn defines a new first-order formula of Heyting arithmetic which we can denote, say, $ n\mathbin{\mathbf{r}}\varphi$ .

Now I understand that (Dragalin and Troelstra independently proved that) for all $ \varphi$ ,

  1. $ \mathsf{HA} + \mathrm{ECT}_0 \vdash (\varphi \Leftrightarrow \exists n.(n\mathbin{\mathbf{r}}\varphi))$

  2. $ \mathsf{HA} + \mathrm{ECT}_0 \vdash \varphi$ if and only if $ \mathsf{HA} \vdash \exists n.(n\mathbin{\mathbf{r}}\varphi)$

where $ \mathsf{HA}$ denotes Heyting arithmetic and $ \mathrm{ECT}_0$ some statement (the “extended Church thesis”) which I won’t copy because it’s not really germane to my question but which says informally that every relation on an almost negatively defined domain contains a partial recursive function defined on that domain; note that $ \mathrm{ECT}_0$ is classically refutable.

Furthermore, in (2) (well, trivially in (1) also), $ \mathsf{HA}$ can be replaced by $ \mathsf{HA} + \mathrm{MP}$ , where $ \mathrm{MP}$ (“Markov’s principle”) is the (classically tautological) $ (\forall x.(\psi(x)\lor\neg\psi(x))) \Rightarrow ((\neg\neg\exists x.\psi(x))\Rightarrow \exists x.\psi(x))$ .

To paraphrase, $ \mathsf{HA} + \mathrm{ECT}_0$ axiomatizes the set of formulae provably realizable in $ \mathsf{HA}$ , and $ \mathsf{HA} + \mathrm{MP} + \mathrm{ECT}_0$ axiomatizes the set of formulae provably realizable in $ \mathsf{HA} + \mathrm{MP}$ .

This leads me to ask:

Question: what can be said about the set of formulae $ \varphi$ such that $ \mathsf{PA} \vdash \exists n.(n\mathbin{\mathbf{r}}\varphi)$ , where $ \mathsf{PA}$ denotes Peano arithmetic (i.e., Heyting arithmetic plus the excluded middle)? In other words, what are the set of formulae provably realizable in Peano arithmetic? Can they be axiomatized?