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

  • Thread starter Thread starter evinda
  • Start date Start date
  • Tags Tags
    Language
AI Thread Summary
The discussion focuses on the definitions and roles of $\phi$ and $\phi'$ in regular grammars, specifically in the context of grammar rules and the generation of strings. Participants clarify that $\phi$ and $\phi'$ represent substrings surrounding a non-terminal in the production rules, and that each string in the sequence can be derived from the previous one using specific grammar rules. There is a consensus that for each word in the language generated by the grammar, there exists a unique sequence of transformations, and that $\phi_k$ and $\phi_k'$ can vary across different steps. Examples are provided to illustrate how these components interact within the grammar's structure. Overall, the conversation aims to clarify the mechanics of regular grammars and the significance of these symbols in string generation.
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
13K
Replies
16
Views
6K
4
Replies
175
Views
25K
Back
Top