{"group":{"id":1,"name":"Community","lockable":false,"created_at":"2012-01-18T18:02:15.000Z","updated_at":"2025-12-14T01:33:56.000Z","description":"Problems submitted by members of the MATLAB Central community.","is_default":true,"created_by":161519,"badge_id":null,"featured":false,"trending":false,"solution_count_in_trending_period":0,"trending_last_calculated":"2025-12-14T00:00:00.000Z","image_id":null,"published":true,"community_created":false,"status_id":2,"is_default_group_for_player":false,"deleted_by":null,"deleted_at":null,"restored_by":null,"restored_at":null,"description_opc":null,"description_html":null,"published_at":null},"problems":[{"id":60964,"title":"Evaluate Deterministic Finite Automata on String","description":"Given a Deterministic Finite Automata (DFA) and a string, determine whether or not the DFA will accept when ran on the string. Assume the first state is always the starting state.\r\nTransitions will be given as an mx3 array of ints (where m is the number of state transitions), where each row will represent a state transition. The first element of the row will be the state we're transitioning from, the second will be the state we're transitioning to, and the third will be the ascii value of the character we're transitioning over. Assume the automata you are given are deterministic (e.g. there will either be one transition you can take, in which case you should take it, or there will be none, in which case you should return false).\r\nSince the alphabet is arbitrary integers the DFA will not be exhaustive. If there is no transition over the current character for a given state, return false.\r\nEx: If we're given the following DFA\r\ntransitions=double([1 2 'a'; 2 3 'a'; 2 3 'b']), finals=[3]\r\nwhen s='ab' or s='aa' we should return true, otherwise we should return false. For more complex examples, see the tests.\r\nFor information about DFAs see https://en.wikipedia.org/wiki/Deterministic_finite_automaton","description_html":"\u003cdiv style = \"text-align: start; line-height: 20.4333px; min-height: 0px; white-space: normal; color: rgb(0, 0, 0); font-family: Menlo, Monaco, Consolas, monospace; font-style: normal; font-size: 14px; font-weight: 400; text-decoration: rgb(0, 0, 0); white-space: normal; \"\u003e\u003cdiv style=\"block-size: 327px; display: block; min-width: 0px; padding-block-start: 0px; padding-top: 0px; perspective-origin: 408px 163.5px; transform-origin: 408px 163.5px; vertical-align: baseline; \"\u003e\u003cdiv style=\"block-size: 42px; font-family: Helvetica, Arial, sans-serif; line-height: 21px; margin-block-end: 9px; margin-block-start: 2px; margin-bottom: 9px; margin-inline-end: 10px; margin-inline-start: 4px; margin-left: 4px; margin-right: 10px; margin-top: 2px; perspective-origin: 385px 21px; text-align: left; transform-origin: 385px 21px; white-space-collapse: preserve; margin-left: 4px; margin-top: 2px; margin-bottom: 9px; margin-right: 10px; \"\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 373.408px 8px; transform-origin: 373.408px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003eGiven a Deterministic Finite Automata (DFA) and a string, determine whether or not the DFA will accept when ran on the string. Assume the first state is always the starting state.\u003c/span\u003e\u003c/span\u003e\u003c/div\u003e\u003cdiv style=\"block-size: 105px; font-family: Helvetica, Arial, sans-serif; line-height: 21px; margin-block-end: 9px; margin-block-start: 2px; margin-bottom: 9px; margin-inline-end: 10px; margin-inline-start: 4px; margin-left: 4px; margin-right: 10px; margin-top: 2px; perspective-origin: 385px 52.5px; text-align: left; transform-origin: 385px 52.5px; white-space-collapse: preserve; margin-left: 4px; margin-top: 2px; margin-bottom: 9px; margin-right: 10px; \"\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 381.708px 8px; transform-origin: 381.708px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003eTransitions will be given as an mx3 array of ints (where m is the number of state transitions), where each row will represent a state transition. The first element of the row will be the state we're transitioning from, the second will be the state we're transitioning to, and the third will be the ascii value of the character we're transitioning over. Assume the automata you are given are deterministic (e.g. there will either be one transition you can take, in which case you should take it, or there will be none, in which case you should return false).\u003c/span\u003e\u003c/span\u003e\u003c/div\u003e\u003cdiv style=\"block-size: 42px; font-family: Helvetica, Arial, sans-serif; line-height: 21px; margin-block-end: 9px; margin-block-start: 2px; margin-bottom: 9px; margin-inline-end: 10px; margin-inline-start: 4px; margin-left: 4px; margin-right: 10px; margin-top: 2px; perspective-origin: 385px 21px; text-align: left; transform-origin: 385px 21px; white-space-collapse: preserve; margin-left: 4px; margin-top: 2px; margin-bottom: 9px; margin-right: 10px; \"\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 381.958px 8px; transform-origin: 381.958px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003eSince the alphabet is arbitrary integers the DFA will not be exhaustive. If there is no transition over the current character for a given state, return false.\u003c/span\u003e\u003c/span\u003e\u003c/div\u003e\u003cdiv style=\"block-size: 21px; font-family: Helvetica, Arial, sans-serif; line-height: 21px; margin-block-end: 9px; margin-block-start: 2px; margin-bottom: 9px; margin-inline-end: 10px; margin-inline-start: 4px; margin-left: 4px; margin-right: 10px; margin-top: 2px; perspective-origin: 385px 10.5px; text-align: left; transform-origin: 385px 10.5px; white-space-collapse: preserve; margin-left: 4px; margin-top: 2px; margin-bottom: 9px; margin-right: 10px; \"\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 109.467px 8px; transform-origin: 109.467px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003eEx: If we're given the following DFA\u003c/span\u003e\u003c/span\u003e\u003c/div\u003e\u003cdiv style=\"block-size: 21px; font-family: Helvetica, Arial, sans-serif; line-height: 21px; margin-block-end: 9px; margin-block-start: 2px; margin-bottom: 9px; margin-inline-end: 10px; margin-inline-start: 4px; margin-left: 4px; margin-right: 10px; margin-top: 2px; perspective-origin: 385px 10.5px; text-align: left; transform-origin: 385px 10.5px; white-space-collapse: preserve; margin-left: 4px; margin-top: 2px; margin-bottom: 9px; margin-right: 10px; \"\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 160.092px 8px; transform-origin: 160.092px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003etransitions=double([1 2 'a'; 2 3 'a'; 2 3 'b']), finals=[3]\u003c/span\u003e\u003c/span\u003e\u003c/div\u003e\u003cdiv style=\"block-size: 21px; font-family: Helvetica, Arial, sans-serif; line-height: 21px; margin-block-end: 9px; margin-block-start: 2px; margin-bottom: 9px; margin-inline-end: 10px; margin-inline-start: 4px; margin-left: 4px; margin-right: 10px; margin-top: 2px; perspective-origin: 385px 10.5px; text-align: left; transform-origin: 385px 10.5px; white-space-collapse: preserve; margin-left: 4px; margin-top: 2px; margin-bottom: 9px; margin-right: 10px; \"\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 374.475px 8px; transform-origin: 374.475px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003ewhen s='ab' or s='aa' we should return true, otherwise we should return false. For more complex examples, see the tests.\u003c/span\u003e\u003c/span\u003e\u003c/div\u003e\u003cdiv style=\"block-size: 21px; font-family: Helvetica, Arial, sans-serif; line-height: 21px; margin-block-end: 9px; margin-block-start: 2px; margin-bottom: 9px; margin-inline-end: 10px; margin-inline-start: 4px; margin-left: 4px; margin-right: 10px; margin-top: 2px; perspective-origin: 385px 10.5px; text-align: left; transform-origin: 385px 10.5px; white-space-collapse: preserve; margin-left: 4px; margin-top: 2px; margin-bottom: 9px; margin-right: 10px; \"\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 100.742px 8px; transform-origin: 100.742px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003eFor information about DFAs see \u003c/span\u003e\u003c/span\u003e\u003ca target='_blank' href = \"https://en.wikipedia.org/wiki/Deterministic_finite_automaton\"\u003e\u003cspan style=\"\"\u003e\u003cspan style=\"\"\u003ehttps://en.wikipedia.org/wiki/Deterministic_finite_automaton\u003c/span\u003e\u003c/span\u003e\u003c/a\u003e\u003c/div\u003e\u003c/div\u003e\u003c/div\u003e","function_template":"function accepts = dfa(transitions, finals, s)\r\n  accepts = false;\r\n  state = 1;\r\nend","test_suite":"%%\r\ntransitions=double([1 2 'a'; 2 3 'a'; 2 3 'b']);\r\nfinals=[3];\r\nassert(dfa(transitions, finals, 'aa'))\r\nassert(dfa(transitions, finals, 'ab'))\r\nassert(~dfa(transitions, finals, 'ba'))\r\nassert(~dfa(transitions, finals, 'ac'))\r\nassert(~dfa(transitions, finals, 'aba'))\r\n%%\r\n% 3-deep matching parenthesis!\r\ntransitions=double([1 2 '('; 2 3 '('; 3 4 '('; 4 3 ')'; 3 2 ')'; 2 1 ')']);\r\nfinals=[1];\r\nassert(dfa(transitions, finals, '((()))'))\r\nassert(dfa(transitions, finals, '()(()())'))\r\nassert(dfa(transitions, finals, '()(()())'))\r\nassert(~dfa(transitions, finals, '((())')) % not matching\r\nassert(~dfa(transitions, finals, '(((())))')) % too deep\r\n%%\r\n% numbers x, y and z such that it accepts if x+y=z, where the input is the binary \r\n% representation of x y and z put adjacent to each other, e.g. x1y1z1x2y2z2...xnynzn\r\nx = randi([0, 31]);\r\ny = randi([0, 31]);\r\nz = x + y;\r\ns = reshape(fliplr(dec2bin([x y z])),[],1)'; % create the string representation\r\ntransitions=double([\r\n    1 2 '0';\r\n    1 5 '1';\r\n    2 3 '0';\r\n    2 4 '1';\r\n    3 1 '0';\r\n    4 1 '1';\r\n    5 6 '0';\r\n    5 7 '1';\r\n    6 1 '1';\r\n    7 8 '0';\r\n    8 9 '0';\r\n    8 12 '1';\r\n    9 11 '0';\r\n    9 10 '1';\r\n    10 8 '0';\r\n    11 1 '1';\r\n    12 14 '0';\r\n    12 13 '1';\r\n    13 8 '1';\r\n    14 8 '0';\r\n]);\r\nfinals=[1, 8];\r\nassert(dfa(transitions, finals, s))\r\n% make a failing solution\r\nwhile z == x + y\r\n    z = randi([0, 61]);\r\nend\r\ns = reshape(fliplr(dec2bin([x y z])),[],1)';\r\nassert(~dfa(transitions, finals, s))","published":true,"deleted":false,"likes_count":26,"comments_count":3,"created_by":4913739,"edited_by":4913739,"edited_at":"2025-08-11T13:36:37.000Z","deleted_by":null,"deleted_at":null,"solvers_count":12,"test_suite_updated_at":"2025-07-18T14:36:00.000Z","rescore_all_solutions":false,"group_id":1,"created_at":"2025-07-16T15:20:48.000Z","updated_at":"2026-04-03T11:38:46.000Z","published_at":"2025-07-16T15:21:15.000Z","restored_at":null,"restored_by":null,"spam":null,"simulink":false,"admin_reviewed":false,"description_opc":"{\"parts\":[{\"partUri\":\"/matlab/document.xml\",\"contentType\":\"application/vnd.mathworks.matlab.code.document+xml\",\"content\":\"\u003c?xml version=\\\"1.0\\\" encoding=\\\"UTF-8\\\"?\u003e\u003cw:document xmlns:w=\\\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\\\"\u003e\u003cw:body\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003cw:jc w:val=\\\"left\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eGiven a Deterministic Finite Automata (DFA) and a string, determine whether or not the DFA will accept when ran on the string. Assume the first state is always the starting state.\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003cw:jc w:val=\\\"left\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eTransitions will be given as an mx3 array of ints (where m is the number of state transitions), where each row will represent a state transition. The first element of the row will be the state we're transitioning from, the second will be the state we're transitioning to, and the third will be the ascii value of the character we're transitioning over. Assume the automata you are given are deterministic (e.g. there will either be one transition you can take, in which case you should take it, or there will be none, in which case you should return false).\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003cw:jc w:val=\\\"left\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eSince the alphabet is arbitrary integers the DFA will not be exhaustive. If there is no transition over the current character for a given state, return false.\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003cw:jc w:val=\\\"left\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eEx: If we're given the following DFA\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003cw:jc w:val=\\\"left\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003etransitions=double([1 2 'a'; 2 3 'a'; 2 3 'b']), finals=[3]\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003cw:jc w:val=\\\"left\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003ewhen s='ab' or s='aa' we should return true, otherwise we should return false. For more complex examples, see the tests.\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003cw:jc w:val=\\\"left\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eFor information about DFAs see \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:hyperlink w:docLocation=\\\"https://en.wikipedia.org/wiki/Deterministic_finite_automaton\\\"\u003e\u003cw:r\u003e\u003cw:t\u003ehttps://en.wikipedia.org/wiki/Deterministic_finite_automaton\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:hyperlink\u003e\u003c/w:p\u003e\u003c/w:body\u003e\u003c/w:document\u003e\",\"relationship\":null}],\"relationships\":[{\"relationshipType\":\"http://schemas.mathworks.com/matlab/code/2013/relationships/document\",\"target\":\"/matlab/document.xml\",\"relationshipId\":\"rId1\"}]}"}],"problem_search":{"errors":[],"problems":[{"id":60964,"title":"Evaluate Deterministic Finite Automata on String","description":"Given a Deterministic Finite Automata (DFA) and a string, determine whether or not the DFA will accept when ran on the string. Assume the first state is always the starting state.\r\nTransitions will be given as an mx3 array of ints (where m is the number of state transitions), where each row will represent a state transition. The first element of the row will be the state we're transitioning from, the second will be the state we're transitioning to, and the third will be the ascii value of the character we're transitioning over. Assume the automata you are given are deterministic (e.g. there will either be one transition you can take, in which case you should take it, or there will be none, in which case you should return false).\r\nSince the alphabet is arbitrary integers the DFA will not be exhaustive. If there is no transition over the current character for a given state, return false.\r\nEx: If we're given the following DFA\r\ntransitions=double([1 2 'a'; 2 3 'a'; 2 3 'b']), finals=[3]\r\nwhen s='ab' or s='aa' we should return true, otherwise we should return false. For more complex examples, see the tests.\r\nFor information about DFAs see https://en.wikipedia.org/wiki/Deterministic_finite_automaton","description_html":"\u003cdiv style = \"text-align: start; line-height: 20.4333px; min-height: 0px; white-space: normal; color: rgb(0, 0, 0); font-family: Menlo, Monaco, Consolas, monospace; font-style: normal; font-size: 14px; font-weight: 400; text-decoration: rgb(0, 0, 0); white-space: normal; \"\u003e\u003cdiv style=\"block-size: 327px; display: block; min-width: 0px; padding-block-start: 0px; padding-top: 0px; perspective-origin: 408px 163.5px; transform-origin: 408px 163.5px; vertical-align: baseline; \"\u003e\u003cdiv style=\"block-size: 42px; font-family: Helvetica, Arial, sans-serif; line-height: 21px; margin-block-end: 9px; margin-block-start: 2px; margin-bottom: 9px; margin-inline-end: 10px; margin-inline-start: 4px; margin-left: 4px; margin-right: 10px; margin-top: 2px; perspective-origin: 385px 21px; text-align: left; transform-origin: 385px 21px; white-space-collapse: preserve; margin-left: 4px; margin-top: 2px; margin-bottom: 9px; margin-right: 10px; \"\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 373.408px 8px; transform-origin: 373.408px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003eGiven a Deterministic Finite Automata (DFA) and a string, determine whether or not the DFA will accept when ran on the string. Assume the first state is always the starting state.\u003c/span\u003e\u003c/span\u003e\u003c/div\u003e\u003cdiv style=\"block-size: 105px; font-family: Helvetica, Arial, sans-serif; line-height: 21px; margin-block-end: 9px; margin-block-start: 2px; margin-bottom: 9px; margin-inline-end: 10px; margin-inline-start: 4px; margin-left: 4px; margin-right: 10px; margin-top: 2px; perspective-origin: 385px 52.5px; text-align: left; transform-origin: 385px 52.5px; white-space-collapse: preserve; margin-left: 4px; margin-top: 2px; margin-bottom: 9px; margin-right: 10px; \"\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 381.708px 8px; transform-origin: 381.708px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003eTransitions will be given as an mx3 array of ints (where m is the number of state transitions), where each row will represent a state transition. The first element of the row will be the state we're transitioning from, the second will be the state we're transitioning to, and the third will be the ascii value of the character we're transitioning over. Assume the automata you are given are deterministic (e.g. there will either be one transition you can take, in which case you should take it, or there will be none, in which case you should return false).\u003c/span\u003e\u003c/span\u003e\u003c/div\u003e\u003cdiv style=\"block-size: 42px; font-family: Helvetica, Arial, sans-serif; line-height: 21px; margin-block-end: 9px; margin-block-start: 2px; margin-bottom: 9px; margin-inline-end: 10px; margin-inline-start: 4px; margin-left: 4px; margin-right: 10px; margin-top: 2px; perspective-origin: 385px 21px; text-align: left; transform-origin: 385px 21px; white-space-collapse: preserve; margin-left: 4px; margin-top: 2px; margin-bottom: 9px; margin-right: 10px; \"\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 381.958px 8px; transform-origin: 381.958px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003eSince the alphabet is arbitrary integers the DFA will not be exhaustive. If there is no transition over the current character for a given state, return false.\u003c/span\u003e\u003c/span\u003e\u003c/div\u003e\u003cdiv style=\"block-size: 21px; font-family: Helvetica, Arial, sans-serif; line-height: 21px; margin-block-end: 9px; margin-block-start: 2px; margin-bottom: 9px; margin-inline-end: 10px; margin-inline-start: 4px; margin-left: 4px; margin-right: 10px; margin-top: 2px; perspective-origin: 385px 10.5px; text-align: left; transform-origin: 385px 10.5px; white-space-collapse: preserve; margin-left: 4px; margin-top: 2px; margin-bottom: 9px; margin-right: 10px; \"\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 109.467px 8px; transform-origin: 109.467px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003eEx: If we're given the following DFA\u003c/span\u003e\u003c/span\u003e\u003c/div\u003e\u003cdiv style=\"block-size: 21px; font-family: Helvetica, Arial, sans-serif; line-height: 21px; margin-block-end: 9px; margin-block-start: 2px; margin-bottom: 9px; margin-inline-end: 10px; margin-inline-start: 4px; margin-left: 4px; margin-right: 10px; margin-top: 2px; perspective-origin: 385px 10.5px; text-align: left; transform-origin: 385px 10.5px; white-space-collapse: preserve; margin-left: 4px; margin-top: 2px; margin-bottom: 9px; margin-right: 10px; \"\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 160.092px 8px; transform-origin: 160.092px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003etransitions=double([1 2 'a'; 2 3 'a'; 2 3 'b']), finals=[3]\u003c/span\u003e\u003c/span\u003e\u003c/div\u003e\u003cdiv style=\"block-size: 21px; font-family: Helvetica, Arial, sans-serif; line-height: 21px; margin-block-end: 9px; margin-block-start: 2px; margin-bottom: 9px; margin-inline-end: 10px; margin-inline-start: 4px; margin-left: 4px; margin-right: 10px; margin-top: 2px; perspective-origin: 385px 10.5px; text-align: left; transform-origin: 385px 10.5px; white-space-collapse: preserve; margin-left: 4px; margin-top: 2px; margin-bottom: 9px; margin-right: 10px; \"\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 374.475px 8px; transform-origin: 374.475px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003ewhen s='ab' or s='aa' we should return true, otherwise we should return false. For more complex examples, see the tests.\u003c/span\u003e\u003c/span\u003e\u003c/div\u003e\u003cdiv style=\"block-size: 21px; font-family: Helvetica, Arial, sans-serif; line-height: 21px; margin-block-end: 9px; margin-block-start: 2px; margin-bottom: 9px; margin-inline-end: 10px; margin-inline-start: 4px; margin-left: 4px; margin-right: 10px; margin-top: 2px; perspective-origin: 385px 10.5px; text-align: left; transform-origin: 385px 10.5px; white-space-collapse: preserve; margin-left: 4px; margin-top: 2px; margin-bottom: 9px; margin-right: 10px; \"\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 100.742px 8px; transform-origin: 100.742px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003eFor information about DFAs see \u003c/span\u003e\u003c/span\u003e\u003ca target='_blank' href = \"https://en.wikipedia.org/wiki/Deterministic_finite_automaton\"\u003e\u003cspan style=\"\"\u003e\u003cspan style=\"\"\u003ehttps://en.wikipedia.org/wiki/Deterministic_finite_automaton\u003c/span\u003e\u003c/span\u003e\u003c/a\u003e\u003c/div\u003e\u003c/div\u003e\u003c/div\u003e","function_template":"function accepts = dfa(transitions, finals, s)\r\n  accepts = false;\r\n  state = 1;\r\nend","test_suite":"%%\r\ntransitions=double([1 2 'a'; 2 3 'a'; 2 3 'b']);\r\nfinals=[3];\r\nassert(dfa(transitions, finals, 'aa'))\r\nassert(dfa(transitions, finals, 'ab'))\r\nassert(~dfa(transitions, finals, 'ba'))\r\nassert(~dfa(transitions, finals, 'ac'))\r\nassert(~dfa(transitions, finals, 'aba'))\r\n%%\r\n% 3-deep matching parenthesis!\r\ntransitions=double([1 2 '('; 2 3 '('; 3 4 '('; 4 3 ')'; 3 2 ')'; 2 1 ')']);\r\nfinals=[1];\r\nassert(dfa(transitions, finals, '((()))'))\r\nassert(dfa(transitions, finals, '()(()())'))\r\nassert(dfa(transitions, finals, '()(()())'))\r\nassert(~dfa(transitions, finals, '((())')) % not matching\r\nassert(~dfa(transitions, finals, '(((())))')) % too deep\r\n%%\r\n% numbers x, y and z such that it accepts if x+y=z, where the input is the binary \r\n% representation of x y and z put adjacent to each other, e.g. x1y1z1x2y2z2...xnynzn\r\nx = randi([0, 31]);\r\ny = randi([0, 31]);\r\nz = x + y;\r\ns = reshape(fliplr(dec2bin([x y z])),[],1)'; % create the string representation\r\ntransitions=double([\r\n    1 2 '0';\r\n    1 5 '1';\r\n    2 3 '0';\r\n    2 4 '1';\r\n    3 1 '0';\r\n    4 1 '1';\r\n    5 6 '0';\r\n    5 7 '1';\r\n    6 1 '1';\r\n    7 8 '0';\r\n    8 9 '0';\r\n    8 12 '1';\r\n    9 11 '0';\r\n    9 10 '1';\r\n    10 8 '0';\r\n    11 1 '1';\r\n    12 14 '0';\r\n    12 13 '1';\r\n    13 8 '1';\r\n    14 8 '0';\r\n]);\r\nfinals=[1, 8];\r\nassert(dfa(transitions, finals, s))\r\n% make a failing solution\r\nwhile z == x + y\r\n    z = randi([0, 61]);\r\nend\r\ns = reshape(fliplr(dec2bin([x y z])),[],1)';\r\nassert(~dfa(transitions, finals, s))","published":true,"deleted":false,"likes_count":26,"comments_count":3,"created_by":4913739,"edited_by":4913739,"edited_at":"2025-08-11T13:36:37.000Z","deleted_by":null,"deleted_at":null,"solvers_count":12,"test_suite_updated_at":"2025-07-18T14:36:00.000Z","rescore_all_solutions":false,"group_id":1,"created_at":"2025-07-16T15:20:48.000Z","updated_at":"2026-04-03T11:38:46.000Z","published_at":"2025-07-16T15:21:15.000Z","restored_at":null,"restored_by":null,"spam":null,"simulink":false,"admin_reviewed":false,"description_opc":"{\"parts\":[{\"partUri\":\"/matlab/document.xml\",\"contentType\":\"application/vnd.mathworks.matlab.code.document+xml\",\"content\":\"\u003c?xml version=\\\"1.0\\\" encoding=\\\"UTF-8\\\"?\u003e\u003cw:document xmlns:w=\\\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\\\"\u003e\u003cw:body\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003cw:jc w:val=\\\"left\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eGiven a Deterministic Finite Automata (DFA) and a string, determine whether or not the DFA will accept when ran on the string. Assume the first state is always the starting state.\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003cw:jc w:val=\\\"left\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eTransitions will be given as an mx3 array of ints (where m is the number of state transitions), where each row will represent a state transition. The first element of the row will be the state we're transitioning from, the second will be the state we're transitioning to, and the third will be the ascii value of the character we're transitioning over. Assume the automata you are given are deterministic (e.g. there will either be one transition you can take, in which case you should take it, or there will be none, in which case you should return false).\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003cw:jc w:val=\\\"left\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eSince the alphabet is arbitrary integers the DFA will not be exhaustive. If there is no transition over the current character for a given state, return false.\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003cw:jc w:val=\\\"left\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eEx: If we're given the following DFA\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003cw:jc w:val=\\\"left\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003etransitions=double([1 2 'a'; 2 3 'a'; 2 3 'b']), finals=[3]\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003cw:jc w:val=\\\"left\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003ewhen s='ab' or s='aa' we should return true, otherwise we should return false. For more complex examples, see the tests.\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003cw:jc w:val=\\\"left\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eFor information about DFAs see \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:hyperlink w:docLocation=\\\"https://en.wikipedia.org/wiki/Deterministic_finite_automaton\\\"\u003e\u003cw:r\u003e\u003cw:t\u003ehttps://en.wikipedia.org/wiki/Deterministic_finite_automaton\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:hyperlink\u003e\u003c/w:p\u003e\u003c/w:body\u003e\u003c/w:document\u003e\",\"relationship\":null}],\"relationships\":[{\"relationshipType\":\"http://schemas.mathworks.com/matlab/code/2013/relationships/document\",\"target\":\"/matlab/document.xml\",\"relationshipId\":\"rId1\"}]}"}],"term":"tag:\"language\"","current_player_id":null,"fields":[{"name":"page","type":"integer","callback":null,"default":1,"directive":null,"facet":null,"facet_method":"and","operator":null,"param":null,"static":null,"prepend":true},{"name":"per_page","type":"integer","callback":null,"default":50,"directive":null,"facet":null,"facet_method":"and","operator":null,"param":null,"static":null,"prepend":true},{"name":"sort","type":"string","callback":null,"default":null,"directive":null,"facet":null,"facet_method":"and","operator":null,"param":null,"static":null,"prepend":true},{"name":"body","type":"text","callback":null,"default":"*:*","directive":null,"facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":false},{"name":"group","type":"string","callback":null,"default":null,"directive":"group","facet":true,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"difficulty_rating_bin","type":"string","callback":null,"default":null,"directive":"difficulty_rating_bin","facet":true,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"id","type":"integer","callback":null,"default":null,"directive":"id","facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"tag","type":"string","callback":null,"default":null,"directive":"tag","facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"product","type":"string","callback":null,"default":null,"directive":"product","facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"created_at","type":"timeframe","callback":{},"default":null,"directive":"created_at","facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"profile_id","type":"integer","callback":null,"default":null,"directive":"author_id","facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"created_by","type":"string","callback":null,"default":null,"directive":"author","facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"player_id","type":"integer","callback":null,"default":null,"directive":"solver_id","facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"player","type":"string","callback":null,"default":null,"directive":"solver","facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"solvers_count","type":"integer","callback":null,"default":null,"directive":"solvers_count","facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"comments_count","type":"integer","callback":null,"default":null,"directive":"comments_count","facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"likes_count","type":"integer","callback":null,"default":null,"directive":"likes_count","facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"leader_id","type":"integer","callback":null,"default":null,"directive":"leader_id","facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"leading_solution","type":"integer","callback":null,"default":null,"directive":"leading_solution","facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true}],"filters":[{"name":"asset_type","type":"string","callback":null,"default":null,"directive":null,"facet":null,"facet_method":"and","operator":null,"param":null,"static":"\"cody:problem\"","prepend":true},{"name":"profile_id","type":"integer","callback":{},"default":null,"directive":null,"facet":null,"facet_method":"and","operator":null,"param":"author_id","static":null,"prepend":true}],"query":{"params":{"per_page":50,"term":"tag:\"language\"","current_player":null,"sort":"map(difficulty_value,0,0,999) asc"},"parser":"MathWorks::Search::Solr::QueryParser","directives":{"term":{"directives":{"tag":[["tag:\"language\"","","\"","language","\""]]}}},"facets":{"#\u003cMathWorks::Search::Field:0x00007f1943e67950\u003e":null,"#\u003cMathWorks::Search::Field:0x00007f1943e678b0\u003e":null},"filters":{"#\u003cMathWorks::Search::Field:0x00007f1943e66eb0\u003e":"\"cody:problem\""},"fields":{"#\u003cMathWorks::Search::Field:0x00007f1943e67bd0\u003e":1,"#\u003cMathWorks::Search::Field:0x00007f1943e67b30\u003e":50,"#\u003cMathWorks::Search::Field:0x00007f1943e67a90\u003e":"map(difficulty_value,0,0,999) asc","#\u003cMathWorks::Search::Field:0x00007f1943e679f0\u003e":"tag:\"language\""},"user_query":{"#\u003cMathWorks::Search::Field:0x00007f1943e679f0\u003e":"tag:\"language\""},"queried_facets":{}},"query_backend":{"connection":{"configuration":{"index_url":"http://index-op-v2/solr/","query_url":"http://search-op-v2/solr/","direct_access_index_urls":["http://index-op-v2/solr/"],"direct_access_query_urls":["http://search-op-v2/solr/"],"timeout":10,"vhost":"search","exchange":"search.topic","heartbeat":30,"pre_index_mode":false,"host":"rabbitmq-eks","port":5672,"username":"search","password":"J3bGPZzQ7asjJcCk","virtual_host":"search","indexer":"amqp","http_logging":"true","core":"cody"},"query_connection":{"uri":"http://search-op-v2/solr/cody/","proxy":null,"connection":{"parallel_manager":null,"headers":{"User-Agent":"Faraday v1.0.1"},"params":{},"options":{"params_encoder":"Faraday::FlatParamsEncoder","proxy":null,"bind":null,"timeout":null,"open_timeout":null,"read_timeout":null,"write_timeout":null,"boundary":null,"oauth":null,"context":null,"on_data":null},"ssl":{"verify":true,"ca_file":null,"ca_path":null,"verify_mode":null,"cert_store":null,"client_cert":null,"client_key":null,"certificate":null,"private_key":null,"verify_depth":null,"version":null,"min_version":null,"max_version":null},"default_parallel_manager":null,"builder":{"adapter":{"name":"Faraday::Adapter::NetHttp","args":[],"block":null},"handlers":[{"name":"Faraday::Response::RaiseError","args":[],"block":null}],"app":{"app":{"ssl_cert_store":{"verify_callback":null,"error":null,"error_string":null,"chain":null,"time":null},"app":{},"connection_options":{},"config_block":null}}},"url_prefix":"http://search-op-v2/solr/cody/","manual_proxy":false,"proxy":null},"update_format":"RSolr::JSON::Generator","update_path":"update","options":{"url":"http://search-op-v2/solr/cody"}}},"query":{"params":{"per_page":50,"term":"tag:\"language\"","current_player":null,"sort":"map(difficulty_value,0,0,999) asc"},"parser":"MathWorks::Search::Solr::QueryParser","directives":{"term":{"directives":{"tag":[["tag:\"language\"","","\"","language","\""]]}}},"facets":{"#\u003cMathWorks::Search::Field:0x00007f1943e67950\u003e":null,"#\u003cMathWorks::Search::Field:0x00007f1943e678b0\u003e":null},"filters":{"#\u003cMathWorks::Search::Field:0x00007f1943e66eb0\u003e":"\"cody:problem\""},"fields":{"#\u003cMathWorks::Search::Field:0x00007f1943e67bd0\u003e":1,"#\u003cMathWorks::Search::Field:0x00007f1943e67b30\u003e":50,"#\u003cMathWorks::Search::Field:0x00007f1943e67a90\u003e":"map(difficulty_value,0,0,999) asc","#\u003cMathWorks::Search::Field:0x00007f1943e679f0\u003e":"tag:\"language\""},"user_query":{"#\u003cMathWorks::Search::Field:0x00007f1943e679f0\u003e":"tag:\"language\""},"queried_facets":{}},"options":{"fields":["id","difficulty_rating"]},"join":" "},"results":[{"id":60964,"difficulty_rating":"medium"}]}}