Exploring Regular Grammars & $\phi,\phi'$ Meaning

[evinda]

Hello! (Wave)

According to the notes of computability theory:

Regular grammars

• Alphabet: $\Sigma=\{ \alpha, \beta, \gamma, \dots\}$
  
• Set of non-terminal letters (countable)=N
  
  $S \in N$
  
  $(N \cap \Sigma= \varnothing)$
  
• Grammar rules (finite): $w \to w'$, where $w,w' \in (\Sigma \cup N)^{\star}$
  
• Regular grammars: $S \to \alpha, S \to A, A \to \alpha B, A \to \alpha$

$\text{ Grammar }: \Gamma$

$$L(\Gamma)=\text{" the language that is produced by the grammar } \Gamma \text{ " }= \{ w \in \Sigma^{\ast} | \text{ There exists a finite sequence } s= w_0, \dots, w_k, \dots, w_n=w, \text{ such that for each } k=0, \dots, n-1 \text{ there exists a grammar rule } \theta \to \theta' \text{ and } w_k \text{ is } w_k = \phi \theta \phi' \text{ and } w_{k+1}= \phi \theta' \phi'\}$$What is meant with $\phi$ and $\phi'$? Don't we have to specify it?

Also shouldn't there be a relation between $w_{k-1}$ and $\theta$ ? Or am I wrong?

 

[Evgeny.Makarov]

$$L(\Gamma)=\text{" the language that is produced by the grammar } \Gamma \text{ " }= \{ w \in \Sigma^{\ast} | \text{ There exists a finite sequence } s= w_0, \dots, w_k, \dots, w_n=w, \text{ such that for each } k=0, \dots, n-1 \text{ there exists a grammar rule } \theta \to \theta' \text{ and } w_k \text{ is } w_k = \phi \theta \phi' \text{ and } w_{k+1}= \phi \theta' \phi'\}$$What is meant with $\phi$ and $\phi'$?

More precisely, the end of the definition above says that for each $k=0, \dots, n-1$ there exist a grammar rule $\theta\to\theta'$ and some words $\phi_k$, $\phi_k'$ such that $w_k = \phi_k \theta \phi_k'$ (which means that $w_k$ is the concatenation of $\phi_k$, $\theta$ and $\phi_k'$) and $w_{k+1} = \phi_k \theta' \phi_k'$.

Also shouldn't there be a relation between $w_{k-1}$ and $\theta$ ?

Each word is converted into the following word, in general, by its own rule. For each word $w$ in the sequence there exists a rule $\theta\to\theta'$ such that the next word is obtained from $w$ by replacing some substring $\theta$ with $\theta'$. The previous word was subject to a different replacement using a different rule, and similarly for the following word.

 

[evinda]

I am a little confused right now...

Do we assume that $w$ can be one of the following?

$$w_0, w_1 , \dots, \text{ or } w_n$$

where $w_k=\phi \theta \phi'$ and $w_{k+1}=\phi \theta' \phi'$

Is it a typo that $w_n=w$?

Or have I understood it wrong?

 

[I like Serena]

I am a little confused right now...

Do we assume that $w$ can be one of the following?

$$w_0, w_1 , \dots, \text{ or } w_n$$

where $w_k=\phi \theta \phi'$ and $w_{k+1}=\phi \theta' \phi'$

Is it a typo that $w_n=w$?

Or have I understood it wrong?

Hey evinda! (Smile)

Let's pick an example.

Suppose we have $\Sigma=\{\alpha\}$, $N=\{S,A\}$, and we have grammar rules $\{S→αAα,A→α\}$.
Then $w=ααα$ is an element of the language, because we have the sequence $w_0=S, w_1=αAα, w_2=ααα$.
What would $\theta_k, {\theta'}_k, \phi_k, {\phi'}_k$ be for $k=0,1$? (Wondering)

 

[Evgeny.Makarov]

It's a good idea to consider an example. But concerning your question...

Do we assume that $w$ can be one of the following?

$$w_0, w_1 , \dots, \text{ or } w_n$$

where $w_k=\phi \theta \phi'$ and $w_{k+1}=\phi \theta' \phi'$

We have $w\in L(\Gamma)$ iff there exist $S=w_0,w_1,\dots,w_{n-1},w_n=w$ such that... and so on. For each $w\in L(\Gamma)$ there is its own sequence $w_0,\dots,w_n$. And we don't say that for each $w\in L(\Gamma)$ there exist some $\phi$ and $\phi'$. No, for each $w\in L(\Gamma)$ there exist an $n$ and $w_0,\dots,w_n$ such that for each $k=0,\dots,n-1$ there exist $\phi$ and $\phi'$ and a rule $\theta\to\theta'$ such that $w_k=\phi\theta\phi'$ and $w_{k+1}=\phi\theta'\phi'$.

Is it a typo that $w_n=w$?

No. There exists a sequence of words ending in $w$.

 

[evinda]

Hey evinda! (Smile)

Let's pick an example.

Suppose we have $\Sigma=\{\alpha\}$, $N=\{S,A\}$, and we have grammar rules $\{S→αAα,A→α\}$.
Then $w=ααα$ is an element of the language, because we have the sequence $w_0=S, w_1=αAα, w_2=ααα$.
What would $\theta_k, {\theta'}_k, \phi_k, {\phi'}_k$ be for $k=0,1$? (Wondering)

Do you maybe mean for $k=1,2$ ?

We have that $w_1=\alpha A \alpha$, so $\phi=\alpha$, $\phi'=\alpha$ and $w_2=\alpha \alpha \alpha$ so the grammar rule $\theta \to \theta'$ that we apply is this one: $A \to \alpha$.

Right? (Thinking)

- - - Updated - - -

It's a good idea to consider an example. But concerning your question...

We have $w\in L(\Gamma)$ iff there exist $S=w_0,w_1,\dots,w_{n-1},w_n=w$ such that... and so on. For each $w\in L(\Gamma)$ there is its own sequence $w_0,\dots,w_n$. And we don't say that for each $w\in L(\Gamma)$ there exist some $\phi$ and $\phi'$. No, for each $w\in L(\Gamma)$ there exist an $n$ and $w_0,\dots,w_n$ such that for each $k=0,\dots,n-1$ there exist $\phi$ and $\phi'$ and a rule $\theta\to\theta'$ such that $w_k=\phi\theta\phi'$ and $w_{k+1}=\phi\theta'\phi'$.

I think that I got the definition now... Thanks for explaining! (Smirk)

 

[Evgeny.Makarov]

Do you maybe mean for $k=1,2$ ?

No, for $k=0,1$.

We have that $w_1=\alpha A \alpha$, so $\phi=\alpha$, $\phi'=\alpha$ and $w_2=\alpha \alpha \alpha$ so the grammar rule $\theta \to \theta'$ that we apply is this one: $A \to \alpha$.

Correct. Be sure to also understand what happens for $k=0$.

 

[I like Serena]

Do you maybe mean for $k=1,2$ ?

We have that $w_1=\alpha A \alpha$, so $\phi=\alpha$, $\phi'=\alpha$ and $w_2=\alpha \alpha \alpha$ so the grammar rule $\theta \to \theta'$ that we apply is this one: $A \to \alpha$.

Right? (Thinking)

I did mean $k=0,1$, and I was referring to the more explicit notation that Evgeny suggested.

And yes, that is right. (Nod)

For $k=0$ we have $w_0=S$, $\phi_0 = {\phi'}_0 = \varepsilon$, $\theta_0=S$, and ${\theta'}_0 = αAα$, where $\varepsilon$ means no symbol at all, which is also an element of $(\Sigma \cup N)^*$. (Nerd)

EDIT: Oh, I see Evgeny beat me to it.

 

[evinda]

For $k=0$ we have $w_0=S$, $\phi_0 = {\phi'}_0 = \varepsilon$, $\theta_0=S$, and ${\theta'}_0 = αAα$, where $\varepsilon$ means no symbol at all, which is also an element of $(\Sigma \cup N)^*$. (Nerd)

So $\phi_k, \phi_k'$ are always $\epsilon$ for $k=0$ and remain unchanged for all $k \geq 1$. Right?

 

[I like Serena]

So $\phi_k, \phi_k'$ are always $\epsilon$ for $k=0$

Yes.

and remain unchanged for all $k \geq 1$. Right?

How so? (Wondering)
They can be different for any $k$.

 

[evinda]

How so? (Wondering)
They can be different for any $k$.

It is only known that $\phi_{k+1}, \phi'_{k+1}$ contain $\phi_k$ and $\phi_k'$ respectively as substrings, right?

 

[I like Serena]

It is only known that $\phi_{k+1}, \phi'_{k+1}$ contain $\phi_k$ and $\phi_k'$ respectively as substrings, right?

Nope. (Shake)

 

[evinda]

Nope. (Shake)

I thought so since a word of the sequence follows from its previous one, applying the grammar rule.

Why isn't it like that? (Thinking)

 

[I like Serena]

I thought so since a word of the sequence follows from its previous one, applying the grammar rule.

Why isn't it like that? (Thinking)

Hmm... can we think of an example grammar and/or an example sequence of words where it isn't the case? (Wondering)

 

[evinda]

Hmm... can we think of an example grammar and/or an example sequence of words where it isn't the case? (Wondering)

How could that be?

 

[I like Serena]

How could that be?

Suppose we have $\{S\to AB, A\to\alpha, B\to\beta\}$ and the sequence $S, AB, \alpha B, \alpha \beta$.
Do we have that $\phi_{k+1}, \phi'_{k+1}$ contain $\phi_k$ and $\phi_k'$ respectively as substrings for every $k$? (Wondering)

 

[evinda]

Suppose we have $\{S\to AB, A\to\alpha, B\to\beta\}$ and the sequence $S, AB, \alpha B, \alpha \beta$.
Do we have that $\phi_{k+1}, \phi'_{k+1}$ contain $\phi_k$ and $\phi_k'$ respectively as substrings for every $k$? (Wondering)

Then we have the following, right?

$$w_0=\epsilon S \epsilon \\ w_1=AB=\epsilon AB \epsilon \\ w_2=\alpha B \epsilon \\ w_3=\alpha \beta$$

But we can write for example $\alpha=\epsilon \alpha$, so in this case it holds...

Or am I wrong?

 

[I like Serena]

Then we have the following, right?

$$w_0=\epsilon S \epsilon \\ w_1=AB=\epsilon AB \epsilon \\ w_2=\alpha B \epsilon \\ w_3=\alpha \beta$$

But we can write for example $\alpha=\epsilon \alpha$, so in this case it holds...

Or am I wrong?

I'm making it:
\begin{array}{|c|c|c|c|} \hline
k &w_k & \phi_k & \phi_k'\\
\hline
0&S & \epsilon &\epsilon \\
1&AB & \epsilon & B \\
2&\alpha B & \alpha & \epsilon\\
3&\alpha \beta \\
\hline
\end{array}

Does it really hold? (Wondering)

 

[evinda]

I'm making it:
\begin{array}{|c|c|c|c|} \hline
k &w_k & \phi_k & \phi_k'\\
\hline
0&S & \epsilon &\epsilon \\
1&AB & \epsilon & B \\
2&\alpha B & \alpha & \epsilon\\
3&\alpha \beta \\
\hline
\end{array}

Does it really hold? (Wondering)

So we can take also as a word a state, right?

 

[I like Serena]

So we can take also as a word a state, right?

Huh?
What do you mean? Which state? (Wondering)

 

[evinda]

Huh?
What do you mean? Which state? (Wondering)

For $k=1$ we have $\phi_k'=B$...

 

[I like Serena]

For $k=1$ we have $\phi_k'=B$...

How is that a state? (Wondering)
It's a string consisting of one non-terminal, although it could also have been some other string of terminals and non-terminals.

 

[evinda]

How is that a state? (Wondering)
It's a string consisting of one non-terminal, although it could also have been some other string of terminals and non-terminals.

Sorry, it would be a state if we would have a DFA.
So always, if we have a non-terminal and this leads to something that does not contain this non-terminal, it will hold that the word $\phi_{k+1}$ that we get is independent on $\phi_k$, right?

 

[I like Serena]

Sorry, it would be a state if we would have a DFA.
So always, if we have a non-terminal, this leads to somethig that does not contain this non-terminal, it will hold that the word $\phi_{k+1}$ that we get is independent on $\phi_k$, right?

That depends on the rules.
If each rule has a single non-terminal on the left side, then in every step one non-terminal is replaced by something else.
Since any non-terminal in the string could be picked next, it's difficult to say something about the relation between $\phi_{k}$ and $\phi_{k+1}$.
With certain restrictions I think we'd see that either the one is a subset of the other, or it's the other way around. (Nerd)

 

[evinda]

That depends on the rules.
If each rule has a single non-terminal on the left side, then in every step one non-terminal is replaced by something else.
Since any non-terminal in the string could be picked next, it's difficult to say something about the relation between $\phi_{k}$ and $\phi_{k+1}$.

Ok...

With certain restrictions I think we'd see that either the one is a subset of the other, or it's the other way around. (Nerd)

In the example you stated, we can consider that $\phi_2'$ is a substring of $\phi_1'$, while $\phi_1$ is a substring of $\phi_2$. Right? (Thinking)