CODEWITHSUNDEEP
context-free-grammarbnfregular-languageformal-languages
LuckyLuke
LuckyLuke

Reputation: 49057

Regular expressions

First of all I do not know if this is the correct translation for what I am asking.

In one of my courses we just stared learning about regular expressions, formal languages and so on. 

Alphabet {1,0,S,R}
Terminals {1,0}
Rules:

S ::= 0
S ::= 1
S ::= 1R
R ::= 1R
R ::= 0R
R ::= 1
R ::= 0

In this case let say that I start with the 1R, then I could keep on going with either 1R or 0R.

If I start with 1R, then just a 1....then the sentence(in this case its binary numbers) is complete right? Because I can't "append" something afterwards, say 1R then I choose 1 and then I choose 1R again?

Thanks in advance, and please retag/move post if its uncorrect.

ADDED:

0  at rule S ::= 0  
1  with S ::= 1  
10 with S ::= 1R, so R ::= 0

How to generate 1100110?

This is not homework, it is an example/question from the powerpoint. I do not get how that is done.

Upvotes: 0

Views: 469

Answers (3)

Null Set
Null Set

Reputation: 5414

What you have there is a regular language, defined using a context free grammar. A regular expression that defines the same language is (0)U(1{0,1}*). In plain english, the regular language contains all strings of 0s and 1s that start with 1, and the string 0.

A context free grammar starts with some initial non-terminal symbol, in this case it appears to be S. You then can replace any non-terminal symbols with a string of symbols according to the production rules listed. It is "done" when the string contains no non-terminal symbols.

In your example, you can only "choose 1R" if there is currently an S or an R in the string to replace. As it happens with this grammar, the first time you replace R with 1, you no longer have any non-terminals to replace, and that production of a string is finished.

Edit: Here is a trace of the production of 1100110.

S  
1R         via S ::= 1R
11R        via R ::= 1R
110R       via R ::= 0R
1100R      via R ::= 0R
11001R     via R ::= 1R
110011R    via R ::= 1R
1100110    via R ::= 0

Upvotes: 3

Andres
Andres

Reputation: 5187

If I start with 1R, then just a 1....then the sentence(in this case its binary numbers) is complete right?

Yes, this is correct. The sentence 11 matches S = 1R = 11.

However with this grammar you could always use R = 1R or R= 0R to add more and more digits to your sentence.

Edit: In response to the question edit:

How to generate 1100110?

1100110 = S = 1R = 11R = 110R = 1100R = 11001R = 110011R = 1100110

Hope that helps you understand.

Good Luck!

Upvotes: 1

Will
Will

Reputation: 895

You are correct. Appending is not allowed, only substitution. However with this language, you could continually make your string longer by choosing "R ::= 1R" or "R ::= 0R", and then substituting for R once again.

Upvotes: 2

Related Questions