1. ## Right Linear Grammars

I have this one problem that I'm stuck on in terms of right linear grammars. I've listed the directions and my current answer below. If you guys could look it over that'd be great:

Write a right-linear grammar for each of the following languages.

1. 0∗ 1∗

A language that has zero more instances of 0 followed by zero more instances of 1.

S 0A
A 0A
A 1A
A 1
A 0

2. ## Re: Right Linear Grammars

Maybe this:

$S \to AB$
$A \to 0A$
$A \to \varepsilon$
$B \to 1B$
$B \to \varepsilon$

Not sure what a right-linear grammar is. I am kinda guessing a little here. It appears to me that you can get expressions like the following:

01100010101010100

Essentially, you are allowing any string that begins with a zero followed by at least one more digit. All digits after the first zero are either zero or one.

3. ## Re: Right Linear Grammars

Here's the formal definition of a Right Linear Grammar:

Formal definition of Right Linear Grammars

A right linear grammar is a 4-tuple <T, N, S, R>, where:

1. N is a finite set of non-terminals

2. T is a finite set of terminals, including the empty string

3. S is the start symbol

4. R is a finite set of rewriting rules of the form A-> xB or A-> x, where A and B
stand for non-terminals and x stands for a terminal.

Formal example:
G1 = <T, N, S, R>, where T = {a, b}, N = {S, A, B}, and

S -> aA

A -> aA

A -> bB

B -> bB

B -> b

4. ## Re: Right Linear Grammars

Then the answer i provided should work

5. ## Re: Right Linear Grammars

Also does this Grammar look right?

(D) (aa∗ bb∗)/c

S→ XY
X→ aaB
B→ bbX
Y → c
X → ε
B → ε

6. ## Re: Right Linear Grammars

Currently, you can only get strings like this:

c
aac
aabbc
aabbaac
aabbaabbc

I'd suggest the following:

$S \to XY$
$X \to aaX$
$X \to bbX$
$X \to \varepsilon$
$Y \to c$

Now, you can get any of the following:
c
aac
bbc
aaaac
aabbc
bbaac
bbbbc
etc.

7. ## Re: Right Linear Grammars

I just re-did the problem and read it as: A language that can end in c or c and a and b with instances of zero or more a’s and zero or more b’s.

I ended up coming up with this grammar:

S → ABC

A → aA

A→ ε

B→ bB

B→ ε

C → c

The reason why I re-did it was because the position of the Kleene star

8. ## Re: Right Linear Grammars

I am by no means an expert on grammars. I am not even sure I understand the notation. What do the parentheses mean? What does the forward slash mean?