Formal Languages and automata theory..
let me know if you know this subject i needed help in this.
i have to give a grammar for the language. and decribe a language
generated by grammar. need a complate explaination . i will send you
my question ones you tell me if you know this subject. i have
following examples so far. so i have total 20 problems like them.
1. {Z -->(Belongs to) {c,d }| begins and ends with same letter} 
 Ex. S --> aaSb|Ac , A --> ccA | EmptyString(X)

---

Request for Question Clarification by maniac-ga on 22 Feb 2006 20:23 PST

Hello Kinal,

Could you clarify a couple points:

Your #1 example looks like a grammar that generates strings like
  cc
  dd
  cdcc
  dddd
but not
  cdd
(begins & ends with the same letter, only allowed letters are c & d)

However, you then have 
  S --> aaSb|Ac
and
  A --> ccA | EmptyString(X)
which appear to be a different grammar generating strings like:
  c
  aacb
  aaaacbb
  aacccb

is this a correct interpretation?

Also, are you looking for two answers (for the two grammars listed) or
20 answers (for the two listed plus 18 more)?

  --Maniac

---

Clarification of Question by kinal-ga on 09 Mar 2006 19:35 PST

in problem 1 and 2 construct an equivalent deterministic finite state
machine: do not remove inaccessible states.
1.
-----------|
   | a     | b     |
  _|__     |__     |
 qo|{q0,q1}| 0     |
 q1|0      |{q2,q3}| 
 q2|0      |{q0,q2}|
 q3|{q2,q3}|0      |

Accepting state -- q3
give the transtiton function of the new machine as a table, as above.
 
2.          
--------------------
   | 0     | 1     |
  _|__     |__     |
 qo|{q1}   | 0     |
 q1|0      |{q1,q2}| 
 q2|{qo,q1}|0      |

Accepting state -- q0
Represent the resulting machine as a diagram.

3. in each of the problem 1 and 2, write down the grammar that
generates the corresponding lanugage.

4.for each grammar G below, construct a nondeterministic finite state
machine accepting L(G):
a. S-->a|bP, P-->aQ|b|bS, Q--> aQ|bQ|aS
b. S --> aS|bA|aB|Z, B-->aA|bA|a, A-->aS|b

5. let M be the machine from problem 4a. using the algorithm presented
in class,construct a deterministic FSM K equivalent to M, and then
remove all the inaccessible state from K.

---

Clarification of Question by kinal-ga on 09 Mar 2006 19:36 PST

i have about 10 more question, i will post them as soon as i get answers of this.
and i dont know how does payments method work here.
let me know about it please 
thanks

hey i can answer those questions.
i can say for sure once i see those

You might prove yourself by explaining the example posted.
It doesn't make sense to me.

Aditya--
how much will you charge me if i have 20 questions plus i need clear
explanation that i can understnad what you are doing

Please note that adityaanand-ga is not a Google Answers Researcher,
and cannot receive compensation here. He is welcome to post free
comments, of course.

Hi Kinal,

----------
Example-1:
----------
  Z -->(Belongs to) {c,d }| begins and ends with same letter
Explanation:

  This grammer accepts/specifies string which is generated by using
only two characters 'c' and/or 'd'. Further, the second statement
specifies that the string must begin and end with the same letter.

So collectively, this grammer accepts/specifies PALINDROME string made
up of only 'c' and 'd' characters.
Some examples of this grammer could be: 
        c, cc, ccc, cccc, cdc, ccdcc, cdcdc, dcd, d, dd


----------
Example-2:
----------
 Ex. S --> aaSb|Ac , A --> ccA | EmptyString(X)
Explanation:

 This grammer accepts/specifies string which is made up of only 3
characters 'a', 'b' and/or 'c'. Further, the first statement states
that the string must satisfy: 2*(number of 'a' character) = (number of
'b' character). And the second statement states that there must be odd
number of 'c' character.

So collectively, this grammer accepts/specifies string with twice the
no. of character of 'a' than no. of character of 'b' and odd number of
'c' character with atleast one 'c' character. And the character
sequence in the string must be a-c-b.
Some of the examples of this grammer could be:
    aacb, aaaacbb, aacccb, aacccccb, aaaacccbb



I'm waiting for the other grammers.

sorry for the late reply Dipak
i would post more question soon. THank a lot for clear explaination
it really helped me.
Thanks again

here are the questions.

in problem 1 and 2 construct an equivalent deterministic finite state
machine: do not remove inaccessible states.
1.
-----------|
   | a     | b     |
  _|__     |__     |
 qo|{q0,q1}| 0     |
 q1|0      |{q2,q3}| 
 q2|0      |{q0,q2}|
 q3|{q2,q3}|0      |

Accepting state -- q3
give the transtiton function of the new machine as a table, as above.
 
2.          
--------------------
   | 0     | 1     |
  _|__     |__     |
 qo|{q1}   | 0     |
 q1|0      |{q1,q2}| 
 q2|{qo,q1}|0      |

Accepting state -- q0
Represent the resulting machine as a diagram.

3. in each of the problem 1 and 2, write down the grammar that
generates the corresponding lanugage.

4.for each grammar G below, construct a nondeterministic finite state
machine accepting L(G):
a. S-->a|bP, P-->aQ|b|bS, Q--> aQ|bQ|aS
b. S --> aS|bA|aB|Z, B-->aA|bA|a, A-->aS|b

5. let M be the machine from problem 4a. using the algorithm presented
in class,construct a deterministic FSM K equivalent to M, and then
remove all the inaccessible state from K.