MHB What Do $\phi$ and $\phi'$ Mean in Regular Grammars?

  • Thread starter Thread starter evinda
  • Start date Start date
  • Tags Tags
    Language
evinda
Gold Member
MHB
Messages
3,741
Reaction score
0
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?
 
Physics news on Phys.org
evinda said:
$$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'$.

evinda said:
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.
 
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?
 
evinda said:
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)
 
It's a good idea to consider an example. But concerning your question...

evinda said:
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'$.

evinda said:
Is it a typo that $w_n=w$?
No. There exists a sequence of words ending in $w$.
 
I like Serena said:
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 - - -

Evgeny.Makarov said:
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)
 
evinda said:
Do you maybe mean for $k=1,2$ ?
No, for $k=0,1$.

evinda said:
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$.
 
evinda said:
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.
 
I like Serena said:
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?
 
  • #10
evinda said:
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$.
 
  • #11
I like Serena said:
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?
 
  • #12
evinda said:
It is only known that $\phi_{k+1}, \phi'_{k+1}$ contain $\phi_k$ and $\phi_k'$ respectively as substrings, right?

Nope. (Shake)
 
  • #13
I like Serena said:
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)
 
  • #14
evinda said:
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)
 
  • #15
I like Serena said:
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? :eek:
 
  • #16
evinda said:
How could that be? :eek:

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)
 
  • #17
I like Serena said:
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?
 
  • #18
evinda said:
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)
 
  • #19
I like Serena said:
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?
 
  • #20
evinda said:
So we can take also as a word a state, right?

Huh? :confused:
What do you mean? Which state? (Wondering)
 
  • #21
I like Serena said:
Huh? :confused:
What do you mean? Which state? (Wondering)

For $k=1$ we have $\phi_k'=B$...
 
  • #22
evinda said:
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.
 
  • #23
I like Serena said:
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?
 
  • #24
evinda said:
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)
 
  • #25
I like Serena said:
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...

I like Serena said:
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)
 

Similar threads

Replies
11
Views
4K
Replies
5
Views
2K
Replies
42
Views
10K
Replies
28
Views
6K
Replies
39
Views
12K
Replies
16
Views
6K
4
Replies
175
Views
25K
Back
Top