Notices
Results 1 to 19 of 19

Thread: Automata Theory Questions

  1. #1 Automata Theory Questions 
    Forum Freshman
    Join Date
    Feb 2014
    Posts
    9
    Im currently studying Automata Theory and i have these questions that i want to answer
    the problem im not sure if i answer them currently
    can anyone help me to solve them properly


    mega.co.nz/#!0g9xyToa!Q1IlCoS646aRgvwu7co9Ep_Ub-b-cd1QCA2ptYFVqoU


    Reply With Quote  
     

  2.  
     

  3. #2  
    Forum Radioactive Isotope MagiMaster's Avatar
    Join Date
    Jul 2006
    Posts
    3,440
    Nobody's going to click that link. Just post your questions here, but be aware that we won't answer homework questions. We can try and point you in the right direction though.


    Reply With Quote  
     

  4. #3  
    Forum Freshman
    Join Date
    Feb 2014
    Posts
    9
    Quote Originally Posted by MagiMaster View Post
    Nobody's going to click that link. Just post your questions here, but be aware that we won't answer homework questions. We can try and point you in the right direction though.
    this is not homework or any of these, im just self study this and i need some proper help
    OK first question like this


    If L={a^n b^n :n>0}, then print any five strings and also describe the language
    If L={a^n b^n :n>=0}, then print any five strings and also describe the language

    any answer?
    Reply With Quote  
     

  5. #4  
    Forum Radioactive Isotope MagiMaster's Avatar
    Join Date
    Jul 2006
    Posts
    3,440
    How far have you gotten? Can you work out any strings of either language?
    Reply With Quote  
     

  6. #5  
    Forum Freshman
    Join Date
    Feb 2014
    Posts
    9
    Quote Originally Posted by MagiMaster View Post
    How far have you gotten? Can you work out any strings of either language?
    no so far
    solution of the first
    ab, aabb, aaabbb, aaaabbbb, aaaaaabbbbb.

    second
    aabb, aaabbb, aaaabbbb, aaaaaabbbbb, aaaaaaabbbbbb.

    i dont know if they are right!!! also what it means by describe the language?
    Reply With Quote  
     

  7. #6  
    Forum Radioactive Isotope MagiMaster's Avatar
    Join Date
    Jul 2006
    Posts
    3,440
    aaaaaabbbbb and aaaaaaabbbbbb are not part of either language, but the rest are OK. Describing the language means writing an English sentence or two that describes what strings the language will generate. So the language {a b^n c : n>0 } would generate strings of the form a followed by one or more b's followed by a c. For these simple languages, there's not a whole lot to describe, but for your two examples, there's at least one important difference between them that your descriptions should capture.
    Reply With Quote  
     

  8. #7  
    Forum Freshman
    Join Date
    Feb 2014
    Posts
    9
    Quote Originally Posted by MagiMaster View Post
    aaaaaabbbbb and aaaaaaabbbbbb are not part of either language, but the rest are OK. Describing the language means writing an English sentence or two that describes what strings the language will generate. So the language {a b^n c : n>0 } would generate strings of the form a followed by one or more b's followed by a c. For these simple languages, there's not a whole lot to describe, but for your two examples, there's at least one important difference between them that your descriptions should capture.
    THANKS I FIGURED THE SOME OF THEM BUT I HAVE SOME OTHER QUESTIONS OTHER THAN IN THE IMAGE



    Find a CFG that generates the language

    Q1(A) - L(G) = { an bm | 0 ≤ n m ≤ 2n}
    Q1(B) - L(G) = { an bm | 0 ≤ n, m}

    WHATS THE DIFFERENCE BETWEEN THE Q1(A) AND Q1(B)?

    ANSWER OF Q1(A) (IS IT RIGHT?)
    S → aSb | aSbb | ^

    ANSWER OF Q1(B)
    ????????????????

    Q2(A) - L(G) = { an bm cm d2n | n 0 , m > 0}
    Q2(B) - L(G) = { an bm cm | n , m > 0}

    WHATS THE DIFFERENCE BETWEEN THE Q2(A) AND Q2(B)?

    ANSWER OF Q2(A) (IS IT RIGHT?)
    S → aSdd | A
    A → bAc | bc

    ANSWER OF Q2(B)????????????????

    CAN YOU HELP ME ANSWER Q2(B) AND Q1(B) ?
    Reply With Quote  
     

  9. #8  
    Forum Radioactive Isotope MagiMaster's Avatar
    Join Date
    Jul 2006
    Posts
    3,440
    Your CFG for Q1(A) and Q2(A) looks fine. You shouldn't have any trouble doing the same thing for Q1(B) and Q2(B), but if you are, where are you getting stuck?

    It also asks what's different about each pair. I suspect it's asking for more than just the superficial differences, but t's hard to tell.
    Reply With Quote  
     

  10. #9  
    Forum Junior TridentBlue's Avatar
    Join Date
    Jan 2013
    Posts
    207
    The n 0 vs n thing really isn't clear to me. What, is n supposed to be raised to a negative power? That makes no sense. Seek clarification with the publisher of the problem.
    Reply With Quote  
     

  11. #10  
    Forum Freshman
    Join Date
    Feb 2014
    Posts
    9
    Quote Originally Posted by MagiMaster View Post
    Your CFG for Q1(A) and Q2(A) looks fine. You shouldn't have any trouble doing the same thing for Q1(B) and Q2(B), but if you are, where are you getting stuck?

    It also asks what's different about each pair. I suspect it's asking for more than just the superficial differences, but t's hard to tell.
    To be honest im studying this by myself, i found something similar for Q1(A) and Q1(B) and i did them by myself
    Will you help me to get Q1(B) and Q2(B) properly?

    ANSWER OF Q1(B) (IS IT RIGHT?)
    S → aSb | aaSbb | ^

    ANSWER OF Q2(B) (IS IT RIGHT?)
    S → aS | A
    A → bA | bc
    Reply With Quote  
     

  12. #11  
    Forum Radioactive Isotope MagiMaster's Avatar
    Join Date
    Jul 2006
    Posts
    3,440
    @TridentBlue, I'm pretty sure that's supposed to mean that both n and m are greater than or equal to 0.

    @hamood, your Q2(B) is close-ish, but your Q1(B) is not right. Try writing out a few sentences from the given languages and then try writing out a few sentences from your grammars. Also, think about why each of the production rules exist. For example, if I gave you the CFG: S -> aS | b, what do those two possible productions tell you? I might also help to draw out some transition diagrams for these.
    Reply With Quote  
     

  13. #12  
    Forum Freshman
    Join Date
    Feb 2014
    Posts
    9
    Quote Originally Posted by MagiMaster View Post
    @TridentBlue, I'm pretty sure that's supposed to mean that both n and m are greater than or equal to 0.

    @hamood, your Q2(B) is close-ish, but your Q1(B) is not right. Try writing out a few sentences from the given languages and then try writing out a few sentences from your grammars. Also, think about why each of the production rules exist. For example, if I gave you the CFG: S -> aS | b, what do those two possible productions tell you? I might also help to draw out some transition diagrams for these.
    ANSWER OF Q1(B) (IS IT RIGHT?)
    S → aSb | ^

    ANSWER OF Q2(B) (IS IT RIGHT?)
    S → aS | A
    A → bA |
    ^

    NOW ?
    Reply With Quote  
     

  14. #13  
    Forum Radioactive Isotope MagiMaster's Avatar
    Join Date
    Jul 2006
    Posts
    3,440
    Have you tried writing out a few of the strings generated by those? Your Q2(B) never generates a c so it can't be correct. Your Q1(B) isn't right either. (It generates the same strings as your second language from post #3, which isn't the same as the language from Q1(B).)
    Reply With Quote  
     

  15. #14  
    Forum Freshman
    Join Date
    Feb 2014
    Posts
    9
    Quote Originally Posted by MagiMaster View Post
    Have you tried writing out a few of the strings generated by those? Your Q2(B) never generates a c so it can't be correct. Your Q1(B) isn't right either. (It generates the same strings as your second language from post #3, which isn't the same as the language from Q1(B).)
    I tried but without luck

    ANSWER OF Q1(B) (IS IT RIGHT?)
    S → aS | b | ^

    ANSWER OF Q2(B)
    S → aS | A
    A → bA | b

    This is my last one i hope its right, if its not can you give me the correct answer so i would know what i did wrong or a hint

    Last edited by hamood_d10; March 2nd, 2014 at 01:57 AM.
    Reply With Quote  
     

  16. #15  
    Forum Radioactive Isotope MagiMaster's Avatar
    Join Date
    Jul 2006
    Posts
    3,440
    Neither are right. Again, your Q2(B) can't generate any c's so it can't possibly be right. You might need to back up a bit and work on some easier problems. I could give you the answers, but I don't think you'd actually learn much from that. I might can walk you through the answer to one of the problems, but I don't have time for that right now.
    Reply With Quote  
     

  17. #16  
    Forum Freshman
    Join Date
    Feb 2014
    Posts
    9
    Quote Originally Posted by MagiMaster View Post
    Neither are right. Again, your Q2(B) can't generate any c's so it can't possibly be right. You might need to back up a bit and work on some easier problems. I could give you the answers, but I don't think you'd actually learn much from that. I might can walk you through the answer to one of the problems, but I don't have time for that right now.
    lol i still not read the whole book yet
    these problems found them online in some PDF files

    ANSWER OF Q1(B)
    S → aSb | ^

    ANSWER OF Q2(B)
    S → aS | A
    A → bA

    i hope i get it right now, i would love if i get the answers maybe i understand a little bit
    Reply With Quote  
     

  18. #17  
    Forum Radioactive Isotope MagiMaster's Avatar
    Join Date
    Jul 2006
    Posts
    3,440
    There's still no c's in your Q2(B). Also, you've already tried that answer for Q1(A) (post #12).

    Let's try the language { (a | b)^n : n > 0 }. That is, the language of any number of a's and b's in any order, but not including the empty string. Think about how you'd build such a string one step at a time. You'd just add either an a or a b to the end of any other string of a's and b's. So what would a CFG production to add an a to the end of a string look like? Well, you have to assume there's a non-terminal at the end to be replaced, and there's no reason not to use S in this case, so that's just be S -> aS. What would a CFG production to add b look like? Besides those two, you need productions to terminate the recursion. For this language, there'd be two such rules (there's two ways a string can end). What would those look like? How would you put the four rules together?
    Reply With Quote  
     

  19. #18  
    Forum Freshman
    Join Date
    Feb 2014
    Posts
    9
    Quote Originally Posted by MagiMaster View Post
    There's still no c's in your Q2(B). Also, you've already tried that answer for Q1(A) (post #12).

    Let's try the language { (a | b)^n : n > 0 }. That is, the language of any number of a's and b's in any order, but not including the empty string. Think about how you'd build such a string one step at a time. You'd just add either an a or a b to the end of any other string of a's and b's. So what would a CFG production to add an a to the end of a string look like? Well, you have to assume there's a non-terminal at the end to be replaced, and there's no reason not to use S in this case, so that's just be S -> aS. What would a CFG production to add b look like? Besides those two, you need productions to terminate the recursion. For this language, there'd be two such rules (there's two ways a string can end). What would those look like? How would you put the four rules together?
    ANSWER OF Q1(B)
    S → aSa | aBa

    ANSWER OF Q2(B)
    S → aSa | aBa
    B → bB | b

    no c in
    Q2(B) means No A
    Reply With Quote  
     

  20. #19  
    Forum Radioactive Isotope MagiMaster's Avatar
    Join Date
    Jul 2006
    Posts
    3,440
    Q1(B) isn't a well formed CFG. There's no productions for the non-terminal B. Also, the terminal b can never show up.

    This Q2(B) is the language { a^n b^m a^n : n, m > 0 }, which isn't what you want. And again, there are no c's. I don't understand your comment on that, but the language you're trying to write a CFG for has c's in it, so your CFG also has to have c's.

    You should step back and work on some simpler examples and try to understand them more fully. Maybe go back over how CFGs work and try and write out a few of the strings produced by them.
    Reply With Quote  
     

Similar Threads

  1. need help in Theory of Automata?
    By Hussamgala in forum Computer Science
    Replies: 7
    Last Post: March 29th, 2013, 12:03 AM
  2. Help Needed - Theory of Automata
    By ahmad.ellahi86 in forum Mathematics
    Replies: 0
    Last Post: November 2nd, 2012, 08:37 AM
  3. Need Help with Automata Theory work.
    By SSJ_Sonikku in forum Computer Science
    Replies: 0
    Last Post: March 30th, 2012, 07:38 AM
  4. Ambiguous and definite automata to deterministic automata
    By tonguim in forum Computer Science
    Replies: 0
    Last Post: February 14th, 2011, 03:00 PM
  5. Help in Theory of Automata
    By adi.shoukat in forum Mathematics
    Replies: 0
    Last Post: December 9th, 2009, 05:30 AM
Bookmarks
Bookmarks
Posting Permissions
  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •