no context: does the following grammar have an inherently ambiguous language?

The grammar is as follows:

$ S rightarrow aaAb | aab | To $

$ A rightarrow aaAb | aAb | epsilon $

I think this grammar has an unequivocal equivalent grammar as follows.

First let's rewrite the grammar in the following way, so that this grammar has the same language as one in question:

$ S rightarrow aaSb | aSb | epsilon $

Because this grammar generates $ L = {a ^ nb ^ m: m le n le 2m } $

This grammar only uses two productions in some order to derive strings and then uses null production to complete the derivation.

So, the idea is that we can order the use of production in such a way that any use of $ S rightarrow aaSb $ Production does not arrive before the use of any production $ S rightarrow aSb $. And following this idea, it is very easy to generate this grammar.

$ S rightarrow aSb | To $

$ A rightarrow aaAb | epsilon $

.

Another argument is as follows:

Why $ 2k_1 + k_2 = n $ Y $ k_1 + k_2 = m $ for some $ not negative spatial integer space k_1, k_2 $. (here $ k_1 $ Y $ k_2 $ corresponds to the production usage number of form $ S rightarrow aSb $ Y $ S rightarrow aaSb $ respectively.)

After solving the previous equations, we find that $ k_1 = m-n $ hence the value of $ k_1 $ It will be unique for any perticular chain. Which means we must use a fixed number of times the production of the form $ S rightarrow aSb $. Which consequently means that in our last rewritten grammar there is a fixed point for a perticular chain where you must perform $ S rightarrow A $.

Please help me with this. I want to know if this language is inherently ambiguous or not?

Algorithms: Count compound words with ambiguous decomposition

I have a set of words $ D $, and I make compound words concatenating a fixed number $ n $ of words from $ D $ (Repeats are allowed). Let's call those words $ n $-composites. I want to know how many different compound words can be formed and how many $ n $-composites can be formed in $ to $ forms for each value of $ to $. For example, yes $ D $ is {hell, hello, open, pen} Y $ n = $ 2, the compound word hellopen can be formed as hell + open or hello + pen, so there are 16 different pairs of words in $ D $, but only 15 different words of 2 compounds on $ D $.

Formally, leave $ mathscr A $ be a finite size alphabet $ ge 2 $, $ D $ a finite set of words in length $ ge 2 $ finished $ mathscr A $Y $ n ge 2 $ an integer The set of valid $ n $compound word is $ C = {u_1 ldots u_n mid (u_1, ldots, u_n) in D ^ n } $. Let's call ambiguity of a word $ w $ The number of $ n $-tuples $ (u_1, ldots, u_n) in D ^ n $ such that $ u_1 ldots u_n = w $. (So, an ambiguity of 0 means that the word is not in $ C $, an ambiguity of 1 means that the word can be broken down uniquely, and larger ambiguities mean words that can be formed in multiple ways).

I would like to calculate the number of different compound words, that is, the size of $ C $. I am also interested in the amount of words with ambiguity. $ to $ for every value of $ to $, and especially the number of unambiguous compounds ($ a = $ 1) Obviously, this can be done by listing all $ | D | ^ n $ combinations and store its multiplicity in a multi-set structure, but that has a huge cost of memory and time. Is there a better way? I have the feeling that it would help build a set of prefixes and suffixes, but I can't understand how to chain them.

If the exact calculation is not practical, you would be satisfied with an estimate. How can I test my dictionary for a reliable estimate? In addition, if there is a method that works well, except in some pathological cases, and it is possible to avoid those pathological cases by eliminating some words of $ D $, that is still fine for my application.

I am specifically interested in the following case of practical use: $ D $ it is a set of a few thousand common words in English (all lower case), and $ n $ It is approximately 3 to 8. The application is the generation of passwords of "correct horse battery staple" style: how much bias is introduced if it does not put spaces between words?

State: when there are two buttons, how do I correctly indicate that one is active without being ambiguous?

I'm a little unsure of whether you intend to use these buttons as buttons or as tabs (for navigation).

If you are using them as buttons, indicating that "one is active" implies that the other is disabled. The key is to make the active button visible with a click / tappable and the opposite for the disabled button. In your example, both buttons look active. To make the disabled button appear less clickable / interchangeable, especially compared to the active button, try to set its opacity to be erased, but still readable. You may also want to consider adding information about tools (when moving the mouse) or a dialog box (when clicking or touching) that explains to the user why the button is disabled.

If you are using them as tabs, they are not exactly buttons. The tabs (or the segmented controllers in iOS) help the navigation since they remain static, with only a change of state, which I assume is the "state response" to which you refer? If this is your use case, many visual attributes are opened without buttons that can be applied to solve your problem.

jsf – when adding omniface library I get WELD-001318: Unable to resolve an ambiguous dependency

I'm using JSF 6.2 in eclipse, I have a p: dataTable that I want the filters to be preserved during the session


Reloading the page in the table does not appear filtered until you click on update to the table by means of a button. What I'm trying to do is make an update to the table when loading the page

import org.omnifaces.util.Ajax;
@ManagedBean (name = "myBean")
@ViewScoped
public class myBean {
List of fix list

@PostConstruct
public void init () {
list = listObjects ()
Ajax.update ("form: table");
}
}

In faces config add this:

  
    org.omnifaces.resourcehandler.UnmappedResourceHandler

Add the project to the omnifaces-2.6.1 library which is what makes it listen, if you like the library, even if you do not add the Ajax line in the bean or the change in faces-config the result is the same

javax.servlet.ServletException: WELD-001318: Unable to resolve an ambiguous dependency between: - Managed bean [class myBean] with qualifiers [@Any @Default], - Handled Bean [class otroBean] with qualifiers [@Any @Default]
javax.faces.webapp.FacesServlet.service (FacesServlet.java:671)
io.undertow.servlet.handlers.ServletHandler.handleRequest (ServletHandler.java:85)
io.undertow.servlet.handlers.security.ServletSecurityRoleHandler.handleRequest (ServletSecurityRoleHandler.java:62)
io.undertow.servlet.handlers.ServletDispatchingHandler.handleRequest (ServletDispatchingHandler.java:36)
org.wildfly.extension.undertow.security.SecurityContextAssociationHandler.handleRequest (SecurityContextAssociationHandler.java:78)
io.undertow.server.handlers.PredicateHandler.handleRequest (PredicateHandler.java:43)
io.undertow.servlet.handlers.security.SSLInformationAssociationHandler.handleRequest (SSLInformationAssociationHandler.java:131)
io.undertow.servlet.handlers.security.ServletAuthenticationCallHandler.handleRequest (ServletAuthenticationCallHandler.java:57)
io.undertow.server.handlers.PredicateHandler.handleRequest (PredicateHandler.java:43)
io.undertow.security.handlers.AbstractConfidentialityHandler.handleRequest (AbstractConfidentialityHandler.java:46)
io.undertow.servlet.handlers.security.ServletConfidentialityConstraintHandler.handleRequest (ServletConfidentialityConstraintHandler.java:64)
io.undertow.security.handlers.AuthenticationMechanismsHandler.handleRequest (AuthenticationMechanismsHandler.java:60)
io.undertow.servlet.handlers.security.CachedAuthenticatedSessionHandler.handleRequest (CachedAuthenticatedSessionHandler.java:77)
io.undertow.security.handlers.NotificationReceiverHandler.handleRequest (NotificationReceiverHandler.java:50)
io.undertow.security.handlers.AbstractSecurityContextAssociationHandler.handleRequest (AbstractSecurityContextAssociationHandler.java:43)
io.undertow.server.handlers.PredicateHandler.handleRequest (PredicateHandler.java:43)
org.wildfly.extension.undertow.security.jacc.JACCContextIdHandler.handleRequest (JACCContextIdHandler.java:61)
io.undertow.server.handlers.PredicateHandler.handleRequest (PredicateHandler.java:43)
io.undertow.server.handlers.PredicateHandler.handleRequest (PredicateHandler.java:43)
io.undertow.servlet.handlers.ServletInitialHandler.handleFirstRequest (ServletInitialHandler.java:292)
io.undertow.servlet.handlers.ServletInitialHandler.access $ 100 (ServletInitialHandler.java:81)
io.undertow.servlet.handlers.ServletInitialHandler $ 2.call (ServletInitialHandler.java:138)
io.undertow.servlet.handlers.ServletInitialHandler $ 2.call (ServletInitialHandler.java:135)
io.undertow.servlet.core.ServletRequestContextThreadSetupAction $ 1.call (ServletRequestContextThreadSetupAction.java:48)
io.undertow.servlet.core.ContextClassLoaderSetupAction $ 1.call (ContextClassLoaderSetupAction.java:43)
io.undertow.servlet.api.LegacyThreadSetupActionWrapper $ 1.call (LegacyThreadSetupActionWrapper.java:44)
io.undertow.servlet.api.LegacyThreadSetupActionWrapper $ 1.call (LegacyThreadSetupActionWrapper.java:44)
io.undertow.servlet.api.LegacyThreadSetupActionWrapper $ 1.call (LegacyThreadSetupActionWrapper.java:44)
io.undertow.servlet.api.LegacyThreadSetupActionWrapper $ 1.call (LegacyThreadSetupActionWrapper.java:44)
io.undertow.servlet.api.LegacyThreadSetupActionWrapper $ 1.call (LegacyThreadSetupActionWrapper.java:44)
io.undertow.servlet.handlers.ServletInitialHandler.dispatchRequest (ServletInitialHandler.java:272)
io.undertow.servlet.handlers.ServletInitialHandler.access $ 000 (ServletInitialHandler.java:81)
io.undertow.servlet.handlers.ServletInitialHandler $ 1.handleRequest (ServletInitialHandler.java:104)
io.undertow.server.Connectors.executeRootHandler (Connectors.java:202)
io.undertow.server.HttpServerExchange $ 1.run (HttpServerExchange.java:805)
java.util.concurrent.ThreadPoolExecutor.runWorker (ThreadPoolExecutor.java:1142)
java.util.concurrent.ThreadPoolExecutor $ Worker.run (ThreadPoolExecutor.java:617)
java.lang.Thread.run (Thread.java:745) 

trace – Are these expressions not the same? The output of Mathematica is ambiguous.

The following graph indicates that the first expression is equal to the second. But how can I use Mathematica to prove it's true?

Plot[(-(Log[(1 - P)/P]/Log in[10])) - (Log in[-(P/(-1 + P))]/Log in[10]), {P, 0, 1}]

An attempt to simplify indicates that the expressions are not the same:

FullSimplify[(-(Log[(1 - P)/P]/Log in[10])) - (Log in[-(P/(-1 + P))]/Log in[10])]

That gives the following answer:

(Log in[-1 + 1/P] + Log[-(P/(-1 + P))])/Log in[10]

enter the description of the image here

automaton – automaton that recognizes ambiguous accepted words of another automaton

Build an NFA that simulates (in a decisive way) two executions of the original NFA in the entry. The NFA also remembers a bit, whether the two races have diverged so far or not. If the bit is disabled and the NFA chooses two different transitions, then it turns it on. The NFA accepts if both executions accept and the bit is activated.

If the original NFA has $ k $ States, then the new NFA will have $ 2k ^ 2 $ You can convert it into a DFA with $ 4 ^ {k ^ 2} $ state

We can reduce the number of states in the corresponding DFA by building the power set directly. In each step, we will remember, for each step, if (i) it is impossible to be in that state, (ii) it is possible to be in that state, but there is a single execution of this type, (iii) it is possible to be in the state , and there are at least two of these executions. A state is accepting if there is an acceptance status of type (iii), or at least two acceptance states of type (ii). This construction uses only $ 3 ^ k $ states, and so it matches your suggestion.

Does the compiler analysis phase ever use ambiguous grammars other than operator grammars to make analysis trees?

The operator precedence analyzer is a bottom-up analyzer that uses even ambiguous grammars in the form of operator grammars to analyze a sequence of tokens.

But is there any analyzer that can use ambiguous grammars (of intrinsically ambiguous languages) that is not an operator language to make analysis trees?

P.S: Motivation of this question to know the nature of other languages ‚Äč‚Äčother than $ DCFL $ Used by the syntax phase of the compiler. And also to understand how the analyzer handles. inherently ambiguous $ DCFL $.

automatons – LR analyzers and ambiguous and non-deterministic grammars

The book of the dragon says:

An ambiguous grammar can never be LR.

And then immediately more says:

For example, consider the grammar of if not:

$ begin {align} stmt rightarrow & textbf {if} expr textbf {then} stmt \
& | textbf {if} expr textbf {then} stmt textbf {else} stmt \
& | textbf {other} end {align} $

If we have a shift we reduce the analyzer in the configuration.

$$
begin {matrix}
STACK AND ENTRANCE \
… textbf {if} expr textbf {then} stmt & textbf {else …}
end {matrix}
$$

we can not say if $ textbf {if} expr textbf {then} stmt $ It is the handle, no matter what appears below it on the stack. Here is a change that reduces the conflict. Depending on what follows $ textbf {else} $** at the entrance, it could be correct to reduce $ textbf {if} expr textbf {then} stmt $, or it could be correct to change $ textbf {else} $ and then look for another $ stmt $
complete the alternative $ textbf {if} expr textbf {then} stmt textbf {else} stmt $.

My question is quite simple. The author starts by saying the fact about the grammar "ambiguous", but then gives an example of a problem with the same prefix of the right sides of two productions (for example, non-deterministic grammar), but it is not really related to the ambiguity of the grammar.

I'm right. Also, what does that mean? The LR grammar can not work with both: non-deterministic and ambiguous grammar?