Lecture "Introduction to Computational Thinking", exercise 1

[essepuntato]

What are all the possible sentences that one can produce using the regular grammar introduced in Section “Historic hero: Noam Chomsky”?

[lelax]

< non-terminal> ::= "terminal" and < non-terminal> ::= "terminal" < non-terminal>

[LudovicaErre]

::= "terminal" ::= "I" ::= "you" ::= "terminal" ::= "write" ::= "read" I write/I read you write/you read

[Pablo751]

< non-terminal > ::= "terminal" < non-terminal > ::= "terminal" < non-terminal >

I write You write I read You read

[olgagolgan]

<non terminal> ::= "terminal"
<non terminal> ::= "terminal" <non terminal>

[angstigone]

< non terminal > : := "terminal" < non terminal > ::= "terminal"

e.g.: < sentence > ::= "I" < verb > < verb > ::= "drive" < verb > ::= "eat".

[martasoricetti]

Using the regular grammar you can produce very simple sentences composed by one terminal symbol or by one terminal symbol and maximun one non-terminal symbol -> ::= "terminal"; ::= "terminal" .

[OrsolaMBorrini]

The regular grammar introduced in that section has these form of production rules:

<non-terminal> ::= "terminal"
<non-terminal> ::= "terminal" <non-terminal>

With the regular grammar provided in the example long sentences are not possible, we can have only short ones:

<sentence> ::= "I" <verb>
<sentence> ::= "you" <verb>
<verb> ::= "write"
<verb> ::= "read"

Sentences produced:

• I write
• I read
• you write
• you read

[Marethyu6]

If I'm not mistaken due to not having taken part to the last part of the class, my reasoning is as follows:

Given the production rules <non-terminal> ::= "terminal" and <non-terminal> ::= "terminal" < non-terminal>

Given that the formalization (?) of the question posed would be like how many possibilities for <non-terminal> = <sentence>

Given that the question posed in this issue doesn't specify the sentences to be limited to the examples presented

all the possible sentences that one can produce using the regular grammar

Given that the concept of "sentence" is a part of language expressing a complete description of an event, by using a verb alone or/and followed by other elements of a particular language, formally (?) as follows <sentence> = <verb> or/and <sentence> = <verb> <additional-element-of-language>

I would therefore answer: there's a (nearly) infinite possible set of sentences, considering any possible language (that existed, existing, that will exist) could consider a sentence complete with most verbs alone, or/and by adding another word to it.

Otherwise, if the question was limited to the examples provided, the correct answer(s) have already been given above before and I'm (it's) late! :P

[CarmenSantaniello]

Production rules of the regular grammar: < non-terminal > ::= "terminal" < non-terminal > ::= "terminal" < non-terminal >

For instance: < sentence > ::= "I" < verb > < sentence > ::= "You" < verb > < verb > ::= "sing" < verb > ::= "play"

Results: I sing You sing I play You play

[ManueleVeggi]

Regular grammar:

::= "I" ::= "you" ::= "write" ::= "read **Possible sentences:** ::= "I" "write" ::= "I" "read" ::= "You" "write" ::= "You" "read"

[francescabudel]

Regular grammar comprehends two types of symbols, terminal symbols and non - terminal symbols. By using these restraints, we can create short and simple sentences, made up by at least one element of each category.

For example: < non-terminal > ::= "terminal" < non-terminal > ::= "terminal" < non-terminal >

Terminal symbols can be identified as the elements contained between the quotation marks and also as the basic units of the language of consideration; so, for example, we could substitute the word terminal with the pronoun "I" or the verb "write". On the other hand, non - terminal symbols are the ones specified between the two angular brackets, capable of identifying all the symbols in the formal grammar and of replacing them by a combination of terminal and non-terminal symbols. If we keep the example provided here as a reference, we can apply a set of production rules and, by doing so, substitute all the left side elements with all the contents on the right side.

So: < verb > ::= "write" < verb > ::= "read" < sentence > ::= "I" < verb > < sentence > ::= "you" < verb >

[mirna-regolo]

Regular grammar allows to create unlimited and concise sentences, synthesizing natural grammar. This language uses symbols in the left-side and right-side of production rules, where terminal specifies non-terminal types:

<non-terminal> : := "terminal" and <non-terminal> ::= "terminal" <non-terminal>

for example a: <sentence> ::= <pronoun> "create" <pronoun> ::= "you" <pronoun> ::= "we" i.e. you create and we create

for example b: <sentence> ::= "I" <verb> <verb> ::= "drink" <verb> ::= "eat" i.e. I drink and I eat

[victorchaix]

The possible sentences possible, using the regular grammar, can be reduced to : < non-terminal > ::= "terminal" and < non-terminal > ::= "terminal" < non-terminal > , where non-terminal are "sentences" "verbs" and "pronouns", and terminals specify these verbs and pronouns

[MaddaGh]

as many before me have already written, the possible sentences according to the example should be: I write I read you write you read

[AmeliaLamargese]

Regular grammars are the less expressive among the four grammar types identified by Chomsky, thus their form of production rules only consists of ::="terminal" and ::="terminal" . As an application of the ::="terminal" production rule, we could have ::="you" , which would need an application of the ::="terminal" production rule to express the value of the as ::="study".

[tommasobattisti]

Regular grammar:

• < non-terminal > ::= "terminal"
• < non-terminal > ::= "terminal" < non-terminal >

[ManuSrivastava1]

In total, 4 sentences can be formed according to the production rules which govern our regular grammar

The first production rules will produce the following 2 sentences -

• I write
• I read

The second production rule will produce the following 2 sentences -

• You write
• You read

[Veronicaonofri]

All the possible sentences that one can produce using the regular grammar are 4: I write, i read, you write and you read.

[essepuntato]

@lelax @angstigone @martasoricetti @Marethyu6 @CarmenSantaniello @francescabudel @mirna-regolo @victorchaix @AmeliaLamargese @tommasobattisti, you defined the general rules of regular grammars and some of you have even defined new examples. However, in that section of the book there is already a particular example of a regular grammar defined (the first rule start with the non-terminal <sentence>), and in this exercise, I was interested in having all the possible sentences that can be produced by using that exemplar grammar.

Another hint for all: in your answers to the various exercises, if you have to write codes (e.g. words between angular brackets) be sure that the correct indent is preserved by previewing your post before publishing it. You can use the Markdown markup ` for showing code inline such as `\<sentence>`, and the ``` environment for defining your code as a block:

```
write your Python code here
```

More info about Markdown can be found at https://guides.github.com/features/mastering-markdown/.

[rahak]

The given production rules for regular grammar are: <non-terminal> ::= "terminal" and <non-terminal> ::= "terminal" <non-terminal>

the Example

<sentence> ::= "I" <verb>
<sentence> ::= "You" <verb>
<verb> ::= "write"
<verb> ::= "read"

Possible sentences are:

I write
I read
You write 
You read

P.S I although I have understood the notation, I would. like to look at more examples.