Automata Theory, including abstract machines, grammars, parsing, grammatical inference, transducers, and finite-state techniques
0
votes
0answers
127 views
Turing Machine question, this is NOT HW
I was having a hard time understanding and solving this question that wants me to show the final tape and figuring out if whether or not the turning machine accepts it or not. I have a list of 20 ...
3
votes
3answers
455 views
Is the language of all strings over the alphabet “a,b,c” with the same number of substrings “ab” & “ba” regular?
Is the language of all strings over the alphabet "a,b,c" with the same number of substrings "ab" & "ba" regular?
I believe the answer is NO, but it is hard to make a formal demonstration of it, ...
1
vote
0answers
88 views
Confusion related to state equivalence of finite state machines
I have this confusion if there are two states of a machine p and q. Let x be an input string such that length of x = k, g be the output function and let g(p,x) and g(q,x) be the output when the input ...
4
votes
3answers
128 views
Deciding equivalence of regular languages
Given two regular expressions $R$ and $S$ on an alphabet $\Sigma$ it is possible to decide their equivalence as follows:
build two finite automata $M_R$ and $M_S$ such that $L(R) = L(M_R)$ and $L(S) ...
2
votes
1answer
112 views
Two elementary question on automaton and language
1.What is the definition for a semigroup(or monoid) recognizing a set of words(or language)?2.Are recognizable,rational and regular equivalent to each other with respect to a language?
PS:The reason ...
1
vote
1answer
44 views
How to construct a context free grammar $G$ such that $L(G) = \{ a^i b^j c^k| j \gt i+k\} $?
How to construct a context free grammar $G$ such that $L(G) = \{ a^i b^j c^k| j \gt i+k\} $?
I don't have much idea how to approach this one. Could some help me to understand how to approach these ...
1
vote
1answer
215 views
A regular expression for the words that don't contain the sequence $ab$ over $\{a,b,c\}$
The following is an exercise in a book I am reading:
Let $\Sigma=\{a,b,c\}$, define $L$ to be the language of all words
over $\Sigma$ that do not contain $ab$ as a sub-word.
Find a regular ...
1
vote
2answers
450 views
NFA to DFA conversion, half the power set
Is there a way to tell when a NFA will use at least half the power set when converted to a DFA. I tried to create a few examples, but i just can't see a pattern that would say whether an NFA will use ...
