logistic_guy
Full Member
- Joined
- Apr 17, 2024
- Messages
- 424
here is the question
Find a phrase-structure grammar that generates each of these languages.
(a) The set of bit strings of the form \(\displaystyle 0^{2n}1^{3n}\), where \(\displaystyle n\) is a nonnegative integer.
(b) The set of bit strings with twice as many \(\displaystyle 0\)s as \(\displaystyle 1\)s.
(c) The set of bit strings of the form \(\displaystyle w^2\), where \(\displaystyle w\) is a bit string.
my attemb
i'll start with (b) because i think it's easy
let me start with simple string \(\displaystyle 001\)
i think changinging the order is allowed so we've another string \(\displaystyle 100\)
i'm not sure if the zeros not stick together is a correct string like \(\displaystyle 010\)
now i've to change the digits with letters
\(\displaystyle A = 0\)
\(\displaystyle B = 1\)
if \(\displaystyle S\) the start state, then my string has the form \(\displaystyle AABS\)
i'm not sure about the case \(\displaystyle ABAS\), so i'm not certain if \(\displaystyle A\) and \(\displaystyle B\) can be written in any sequence
so my production step \(\displaystyle P\)
\(\displaystyle S \to AABS\)
if i'm allowed to change the order, then i've another production step
\(\displaystyle AAB \to BAA\)
\(\displaystyle BAA \to AAB\)
so my phrase-structure grammar
\(\displaystyle G = \{V,T,S,P\}\): set of all letters i use
\(\displaystyle V = \{0,1,A,B,S\}\): set of all alphabets i use
\(\displaystyle T = \{0,1\}\): set of all digits i use
\(\displaystyle S \to AABS\)
\(\displaystyle AAB \to BAA\)
\(\displaystyle BAA \to AAB\)
\(\displaystyle A \to 0\)
\(\displaystyle B \to 1\)
is my solution and analize correct?
Find a phrase-structure grammar that generates each of these languages.
(a) The set of bit strings of the form \(\displaystyle 0^{2n}1^{3n}\), where \(\displaystyle n\) is a nonnegative integer.
(b) The set of bit strings with twice as many \(\displaystyle 0\)s as \(\displaystyle 1\)s.
(c) The set of bit strings of the form \(\displaystyle w^2\), where \(\displaystyle w\) is a bit string.
my attemb
i'll start with (b) because i think it's easy
let me start with simple string \(\displaystyle 001\)
i think changinging the order is allowed so we've another string \(\displaystyle 100\)
i'm not sure if the zeros not stick together is a correct string like \(\displaystyle 010\)
now i've to change the digits with letters
\(\displaystyle A = 0\)
\(\displaystyle B = 1\)
if \(\displaystyle S\) the start state, then my string has the form \(\displaystyle AABS\)
i'm not sure about the case \(\displaystyle ABAS\), so i'm not certain if \(\displaystyle A\) and \(\displaystyle B\) can be written in any sequence
so my production step \(\displaystyle P\)
\(\displaystyle S \to AABS\)
if i'm allowed to change the order, then i've another production step
\(\displaystyle AAB \to BAA\)
\(\displaystyle BAA \to AAB\)
so my phrase-structure grammar
\(\displaystyle G = \{V,T,S,P\}\): set of all letters i use
\(\displaystyle V = \{0,1,A,B,S\}\): set of all alphabets i use
\(\displaystyle T = \{0,1\}\): set of all digits i use
\(\displaystyle S \to AABS\)
\(\displaystyle AAB \to BAA\)
\(\displaystyle BAA \to AAB\)
\(\displaystyle A \to 0\)
\(\displaystyle B \to 1\)
is my solution and analize correct?
Last edited: